Problem statement

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

Solution

In dp(i, j) we keep 1 if it is possible to form string s3 upto i+j symbol from first i elements of s1 and first j elements of s2. Every moment we need to check two at most two neighbors: dp(i, j - 1) and dp(i - 1, j): we need to check if symbol s[i+j+1] is equal to s2[j] and answer is true for dp(i, j-1) and j >= 0, or similar condition for another 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 isInterleave(self, s1, s2, s3):
        @lru_cache(None)
        def dp(i, j):
            if i == -1 and j == -1: return True
            return (j >= 0 and s2[j] == s3[i+j+1] and dp(i, j-1)) or (i >= 0 and s1[i] == s3[i+j+1] and dp(i-1,j))
        
        return len(s1) + len(s2) == len(s3) and dp(len(s1) - 1, len(s2) - 1)