leetcode-go/leetcode/hard/87.go

package main

func isScramble(s1 string, s2 string) bool {
	if s1 == s2 {
		return true
	}
	cnt := make([]int, 26)
	for i := range s1 {
		cnt[s1[i]-'a']++
	}
	for i := range s2 {
		cnt[s2[i]-'a']--
	}
	for i := range cnt {
		if cnt[i] != 0 {
			return false
		}
	}
	n := len(s1)
	for i := 1; i < n; i++ { // Can be spilt at any position!!!
		if isScramble(s1[:i], s2[:i]) && isScramble(s1[i:], s2[i:]) {
			return true
		}
		// Swap sub tree
		if isScramble(s1[:i], s2[n-i:]) && isScramble(s1[i:], s2[:n-i]) {
			return true
		}
	}
	return false
}

// func main() {
// 	println(isScramble("great", "rgeat"))
// 	println(isScramble("abcde", "caebd"))
// }