BiruLyu
8/2/2017 - 8:47 PM

## 87. Scramble String(#).java

public class Solution {
public boolean isScramble(String s1, String s2) {
if(s1.length() != s2.length())
return false;
return isScramble_rec(s1, s2, 0, s1.length() - 1, 0, s2.length() - 1);
}
private boolean isScramble_rec(String str1, String str2, int s1, int e1, int s2, int e2){
if(s1 > e1)
return true;
if(s1 == e1)
return str1.charAt(s1) == str2.charAt(s2);
int[] tail = new int[26];
int h = s2, e = e2;
int diffh = 0, diffe = 0;
int i;
for(i = s1; i <= e1 - 1; i++){
diffh--;
else
diffh++;
if(++tail[str1.charAt(i) - 'a'] <= 0)
diffe--;
else
diffe++;
diffh--;
else
diffh++;
if(--tail[str2.charAt(e--) - 'a'] >= 0)
diffe--;
else
diffe++;
if(diffh == 0){
if(isScramble_rec(str1, str2, s1, i, s2, h-1) && isScramble_rec(str1, str2, i + 1, e1, h, e2))
return true;
}
if(diffe == 0){
if(isScramble_rec(str1, str2, s1, i, e + 1, e2) && isScramble_rec(str1, str2, i + 1, e1, s2, e))
return true;
}
}
return false;
}
}
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;
}
}