public class Solution {
public boolean isScramble(String s1, String s2) {
if (s1.equals(s2)) return true;
int[] letters = new int[26];
for (int i=0; i<s1.length(); i++) {
letters[s1.charAt(i)'a']++;
letters[s2.charAt(i)'a'];
}
for (int i=0; i<26; i++) if (letters[i]!=0) return false;
for (int i=1; i<s1.length(); i++) {
if (isScramble(s1.substring(0,i), s2.substring(0,i))
&& isScramble(s1.substring(i), s2.substring(i))) return true;
if (isScramble(s1.substring(0,i), s2.substring(s2.length()i))
&& isScramble(s1.substring(i), s2.substring(0,s2.length()i))) return true;
}
return false;
}
}
Accepted Java solution


@ranhar The 1st IF is to check the LEFT child of S1 is scramble of LEFT child of S2 AND RIGHT child of S1 is also a scramble of RIGHT child of s2.
When this fails, it means the left and right substrings are swapped.
The 2nd IF statement check for the swap case with LEFT child of S1 and RIGHT child of S2 AND RIGHT child of S1 and LEFT child of S2.
I hope this clear it up.

Nice Solution, but I just add one line to make it better.
directly check length(), if not same return false, we don't need to go through counting all the letters' numbers.Personally thinking this Time complexity should be O(4^n), because one problem are almost divided into 4 sub problem. Please correct me if I am wrong.
public boolean isScramble(String s1, String s2) { if(s1 == null  s2 == null) return false; if(s1.equals(s2)) return true; if(s1.length()!=s2.length()) return false; int[] letters = new int[26]; int len = s1.length(); for(int i = 0; i < len; i++){ letters[s1.charAt(i)'a']++; letters[s2.charAt(i)'a']; } for(int i = 0; i < 26; i++){ if(letters[i]!= 0) return false; } for(int i = 1; i < len; i++){ if(isScramble(s1.substring(0,i), s2.substring(0,i)) && isScramble(s1.substring(i), s2.substring(i))) return true; if(isScramble(s1.substring(0,i), s2.substring(leni)) && isScramble(s1.substring(i), s2.substring(0,leni))) return true; } return false; } }


Golang version:
func isScramble(s1 string, s2 string) bool { if s1 == s2 { return true} letters := make([]int, 26) for i:=0; i < len(letters); i++ { letters[i] = 0 } for i:=0; i < len(s1); i++ { letters[int(s1[i])int('a')]++ letters[int(s2[i])int('a')] } for i:=0; i<26; i++ { if letters[i]!=0 { return false } } for i:=1; i<len(s1); i++ { if isScramble(s1[0:i], s2[0:i]) && isScramble(s1[i:], s2[i:]) { return true } if isScramble(s1[0:i], s2[len(s2)i:]) && isScramble(s1[i:], s2[0:len(s2)i]) { return true } } return false }

@zhangzhaoyu1985 I really got the same puzzle.. How can this algorithm be quicker than the O(n ^ 4) solution? I guess it may because of the test cases?

@rocksvashi Think about the following two strings: "abta" and "tbaa", they're anagrams but not scrambles of each other
