23.03.30 Today’s leetcode

87. Scramble String (hard)

Very Hard For Me, But IDEA is simple with DP

class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        return self.Memoization(s1, s2)

    def Memoization(self, s1: str, s2: str) -> bool:
        if len(s1) != len(s2):
            return False
        cache = dict()

        def dfs(s1: str, s2: str) -> bool:
            if s1 == s2:
                return True
            key = (s1, s2) if s1 < s2 else (s2, s1)
            if key in cache:
                return cache[key]
            # Notice: reversed returns iterator, sorted returns list
            if sorted(s1) != sorted(s2):  # !!! important
                cache[key] = False
                return False
            rs2 = s2[::-1]
            for k in range(1, len(s1)):
                if dfs(s1[:k], s2[:k]) and dfs(s1[k:], s2[k:]):
                    cache[key] = True
                    return True
                if dfs(s1[:k], rs2[:k]) and dfs(s1[k:], rs2[k:]):
                    cache[key] = True
                    return True
            cache[key] = False
            return False

        return dfs(s1, s2)