2026-01-07 21:40:08 +0300 MSK

class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        cache = {}

        def check(s1: str, s2: str) -> bool:
            key = (s1, s2)
            if key in cache:
                return cache[key]
            if s1 == s2:
                cache[key] = True
                return True
            res = False
            for middle in range(1, len(s1)):    
                if (
                    check(s1[:middle], s2[:middle]) 
                    and check(s1[middle:], s2[middle:])    
                ) or (
                    check(s1[:middle], s2[-middle:])
                    and check(s1[middle:], s2[:len(s1) - middle])
                ):
                    res = True
                    break
            cache[key] = res
            return res

        return check(s1, s2)