0087.扰乱字符串

func isScramble(s1 string, s2 string) bool {
	cache := make([][][]int, len(s1))
	for i := 0; i < len(s1); i++ {
		cache[i] = make([][]int, len(s2))
		for j := 0; j < len(s2); j++ {
			cache[i][j] = make([]int, len(s1)+1)
		}
	}
	check := func(a, b, length int) bool {
		cnt_a, cnt_b := [26]int{}, [26]int{}
		for i := a; i < a+length; i++ {
			cnt_a[s1[i]-'a'] += 1
		}
		for i := b; i < b+length; i++ {
			cnt_b[s2[i]-'a'] += 1
		}
		for i := 0; i < 26; i++ {
			if cnt_a[i] != cnt_b[i] {
				return false
			}
		}
		return true
	}
	var dfs func(a, b, length int) bool
	dfs = func(a, b, length int) bool {
		if cache[a][b][length] != 0 {
			return cache[a][b][length] == 1
		}
		if s1[a:a+length] == s2[b:b+length] {
			cache[a][b][length] = 1
			return true
		} else if !check(a, b, length) {
			cache[a][b][length] = -1
			return false
		}

		for i := 1; i < length; i++ {
			if dfs(a, b, i) && dfs(a+i, b+i, length-i) {
				cache[a][b][length] = 1
				return true
			}
			if dfs(a, b+length-i, i) && dfs(a+i, b, length-i) {
				cache[a][b][length] = 1
				return true
			}
		}
		cache[a][b][length] = -1
		return false
	}
	return dfs(0, 0, len(s1))
}