Leetcode 0087. Scramble String

Problem statement

https://leetcode.com/problems/scramble-string/

Solution

Let dp(i, j, k) = 1 whether the substring s1[i:i + k] is a scramble of s2[j:j + k] or not. To check this we need to cut first string in every possible ways and check two possibilities for the second string: dp(i, j, k) = 1 for some 1 <= q < k we have: 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).

Complexity

Time complexity is O(n^4), space complexity is O(n^3).

Code

class Solution:
    def isScramble(self, s1, s2):
        @lru_cache(None)
        def dp(i, j, k):
            if k == 1: return s1[i] == s2[j]
            for q in range(1, k):
                if dp(i, j, q) and dp(i+q, j+q, k-q): return True
                if dp(i, j+k-q, q) and dp(i+q, j, k-q): return True
            return False
        
        return dp(0, 0, len(s1))