LeetCode (Python): 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)$.

class Solution:
    # @return a boolean
    def isScramble(self, s1, s2):
        if len(s1)!=len(s2):
            return False
            
        isScramble=[]
        for i in range(0,len(s1)):
            isScramble.append([])
            for j in range(0, len(s1)):
                isScramble[i].append([])
                for k in range(0, len(s1)):
                    isScramble[i][j].append(None)
        return self.isScrambleRec(s1, s2, 0, 0, len(s1)-1, isScramble)
        
    def isScrambleRec(self, s1, s2, i1, i2, length, isScramble):
        if isScramble[i1][i2][length] != None:
            return isScramble[i1][i2][length]
        if length==0:
            isScramble[i1][i2][length] = (s1[i1]==s2[i2])
        else:
            valid = False
            for l in range(0, length):
                valid = valid 

                  or (self.isScrambleRec(s1,s2,i1,i2,l, isScramble) and self.isScrambleRec(s1,s2,i1+l+1,i2+l+1,length-l-1, isScramble))

                  or (self.isScrambleRec(s1,s2,i1,i2+length-l,l, isScramble) and self.isScrambleRec(s1,s2,i1+l+1,i2,length-l-1, isScramble))
            isScramble[i1][i2][length] = valid
        return isScramble[i1][i2][length]