My O(n^4) solution for your reference


  • 2
    U
    class Solution:
    # @return a boolean
    def isScramble(self, s1, s2):
        n=len(s1)
        if n==0: return True
        table=[[[None for i in range(n+1)] for i2 in range(n)] for i1 in range(n)] #table[i1][i2][i] stores if s1[i1:i1+i] is a scramble of s2[i2:i2+i]
        
        def helper(i1,i2,i):
            if table[i1][i2][i]==None:
                if i==1: 
                    table[i1][i2][i]=(s1[i1]==s2[i2])
                else:
                    result=False
                    for partition in range(1,i):
                        if helper(i1,i2,partition) and helper(i1+partition,i2+partition,i-partition): result=True
                        if helper(i1,i2+i-partition,partition) and helper(i1+partition,i2,i-partition): result=True
                    table[i1][i2][i]=result
            return table[i1][i2][i]
            
        return helper(0,0,n)

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.