Problem statement

https://binarysearch.com/problems/Zipped-String/

Solution

Equal to Leetcode 0097. Interleaving String

Complexity

Time complexity is O(mn), because we have mn states and two transactions from one state to others. Space complexity is O(mn) as well, which can be reduced to O(m + n).

Code

class Solution:
    def solve(self, s1, s2, s3):
        @lru_cache(None)
        def dp(i, j):
            if i == -1 and j == -1: return True
            return (j >= 0 and dp(i, j-1) and s2[j] == s3[i+j+1]) or (i >= 0 and dp(i-1,j) and s1[i] == s3[i+j+1])
        
        return len(s1) + len(s2) == len(s3) and dp(len(s1) - 1, len(s2) - 1)