97. Interleaving String

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

Python

Top Down DP

from functools import cache


class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1) + len(s2) != len(s3):
            return False

        if not s1 or not s2:
            if s1: return s1 == s3
            else: return s2 == s3

        n, m = len(s1), len(s2)

        @cache
        def dp(i1: int, i2: int):
            if i1 == n and i2 == m:
                return True

            return any([
                i1 < n and s1[i1] == s3[i1+i2] and dp(i1+1, i2),
                i2 < m and s2[i2] == s3[i1+i2] and dp(i1, i2+1),
            ])

        return dp(0, 0)