Iterative(dp) and recursive in python


  • 0
    S
    class Solution(object):
    def isScramble1(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        if len(s1)!=len(s2): return False
        length = len(s1)
        dp = [[[False]*(length+1) for i in range (length)] for j in range (length)]
        for k in range (1, length+1):
            for i in range(0, length+1-k):
                for j in range(0, length+1-k):
                    if k ==1:
                        dp[i][j][k] = s1[i]==s2[j]
                    else:
                        for q in range(1, k):
                            if dp[i][j][k]: break
                            else:
                                dp[i][j][k] = dp[i][j][q] and dp[i+q][j+q][k-q] or dp[i][j+k-q][q] and dp[i+q][j][k-q]
        return dp[0][0][length]
    
    def isScramble(self, s1, s2):
        dp = {}
        
        def helper(s1, s2):
            if (s1, s2) in dp:
                return dp[(s1, s2)]
            if len(s1)==1:
                return s1==s2
            if len(s1) != len(s2) or sorted(s1)!= sorted(s2):
                return False
            for i in range (1,len(s1)):
                if helper(s1[:i], s2[:i]) and helper(s1[i:] , s2[i:]) or helper(s1[:i], s2[-i:]) and helper(s1[i:], s2[:-i]):
                    dp[(s1,s2)] = True
                    return True
            dp[(s1,s2)] = False
            return False
        
        return helper(s1, s2)

Log in to reply
 

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