87. Scramble String

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);
    }
}