Leetcode: 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.

Solution:

We use a top-down dynamic approach where we need a 3D array to keep the information, hence the memory complexity is $O(n^3)$.

public class Solution {
    public boolean isScramble(String s1, String s2) {
        if(s1.length()!=s2.length())
            return false;
        Boolean[][][] isScramble= new Boolean [s1.length()][s1.length()][s1.length()];
        return isScramble(s1,s2,0,0,s1.length()-1, isScramble);
    }
    
    private boolean isScramble(String s1, String s2, int index1, int index2, int len, Boolean[][][] isScramble)
    {
        if(isScramble[index1][index2][len] != null)
            return isScramble[index1][index2][len];
        if(len==0)
            isScramble[index1][index2][len] = s1.charAt(index1)==s2.charAt(index2);
        else
        {
            boolean value = false;
            for (int i=0; i<len; i++)
            {
                value = value ||  (isScramble(s1,s2,index1, index2, i, isScramble) && isScramble(s1,s2, index1+i+1,index2+i+1,len-i-1, isScramble)) ||  (isScramble(s1,s2,index1,index2+len-i, i, isScramble) && isScramble(s1,s2,index1+i+1,index2,len-i-1, isScramble));
            }
            isScramble[index1][index2][len] = value;
        }
        return isScramble[index1][index2][len]; 
    }
}