Share a Python solution with memorization 220 ms


  • 1
    P
    class Solution(object):
        def isScramble(self, s1, s2):
            """
            :type s1: str
            :type s2: str
            :rtype: bool
            """
            dp = {}
            def dfs(s1, s2):
                if s1 > s2:
                    return dfs(s2, s1)
                if (s1, s2) not in dp:
                    dp[(s1, s2)] = s1 == s2
                    if not dp[(s1, s2)] and sorted(s1) == sorted(s2):
                        for i in range(1, len(s1)):
                            if (dfs(s1[:i], s2[:i]) and dfs(s1[i:], s2[i:])) or\
                            (dfs(s1[:i], s2[-i:]) and dfs(s1[i:], s2[:-i])):
                                dp[(s1, s2)] = True
                return dp[(s1, s2)]
            return dfs(s1, s2)
    

    The "normal" dp solution is slower than this one.


  • 0
    P
    class Solution(object):
        def isScramble(self, s1, s2):
            """
            :type s1: str
            :type s2: str
            :rtype: bool
            """
            if sorted(s1) != sorted(s2):
                return False
            # check scramble
            n = len(s1)
            # whether s2[j:j + k] is a scramble of s1[i:i + k]
            dp = [[[False for j in range(n)] for i in range(n)] for k in range(n + 1)]
            for i in range(n):
                for j in range(n):
                    if s1[i] == s2[j]:
                        dp[1][i][j] = True
            for k in range(2, n + 1):
                for i in range(n + 1 - k):
                    for j in range(n + 1 - k):
                        # each split might form scramble
                        for p in range(1, k):
                            # no swap or swap is scramble
                            if (dp[p][i][j] and dp[k - p][i + p][j + p])\
                            or (dp[p][i][j + k - p] and dp[k - p][i + p][j]):
                                dp[k][i][j] = True
                                break
            return dp[n][0][0]
    

    460ms


Log in to reply
 

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