Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":
great
/ \\
gr eat
/ \\ / \\
g r e at
/ \\ a t
To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat"
rgeat
/ \\
rg eat
/ \\ / \\
r g e at
/ \\
a t
We say that "rgeat" is a scrambled string of "great".
Similarly, if we continue to swap the children of nodes "eat"
and "at", it produces a scrambled string "rgtae".
rgtae
/ \\
rg tae
/ \\ / \\
r g ta e
/ \\
t a
We say that "rgtae" is a scrambled string of "great".
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
public class Solution {
public boolean isScramble(char [] s1, int start1, int end1, char[] s2, int start2, int end2){
if(end1-start1 != end2-start2)
return false;
boolean needPassdown = false;
int sum1=0, sum2=0;
for(int i = 0; start1+i<=end1; i++){
if(s1[start1 + i] != s2[start2 + i]){
needPassdown = true;
}
sum1 ^= s1[start1 + i];
sum2 ^= s2[start2 + i];
}
if(!needPassdown){
return true;
}
if(sum1!=sum2){
return false;
}
for(int i = 0; i<end1-start1; i++){
if(isScramble(s1, start1, start1+i, s2, start2, start2+i) && isScramble(s1, start1+i+1, end1, s2, start2+i+1, end2))
return true;
if(isScramble(s1, start1, start1+i, s2, end2-i, end2) && isScramble(s1, start1+i+1, end1, s2, start2, end2-i-1))
return true;
}
return false;
}
public boolean isScramble(String s1, String s2) {
if(s1 == null || s2 == null)
return false;
char [] sc1 = s1.toCharArray();
char [] sc2 = s2.toCharArray();
return isScramble(sc1, 0, sc1.length-1, sc2, 0, sc2.length-1);
}
}
