# Leetcode 97. Interleaving String

## 題解

### DP

#### Top Down (記憶化搜索)

利用 i+j 座標檢查 s3 字串是否相符

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        # Time complexity: O(nm)
        # Space complexity: O(nm)
        n = len(s1)
        m = len(s2)
        t = len(s3)
        dp = {}
        def dfs(i: int,j: int):
            if i == n and j == m and i + j == t:
                return True
            if (i,j) in dp:
                return dp[(i,j)]
            combine = i + j
            if i < n and combine < t and s1[i] == s3[combine] and dfs(i+1,j):
                return True
            if j < m and combine < t and s2[j] == s3[combine] and dfs(i,j+1):
                return True
            dp[(i,j)] = False
            return dp[(i,j)]
        return dfs(0,0)

#### Top Down

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        # Time complexity: O(nm)
        # Space complexity: O(nm)
        n = len(s1)
        m = len(s2)
        t = len(s3)
        if n + m != t:
            return False
        dp = [([False] * (m+1)) for i in range(n+1)]
        dp[-1][-1] = True
        for i in range(n,-1,-1):
            for j in range(m,-1,-1):
                combine = i + j
                if i < n and combine < t and s1[i] == s3[combine] and dp[i+1][j]:
                    dp[i][j] = True
                if j < m and combine < t and s2[j] == s3[combine] and dp[i][j+1]:
                    dp[i][j] = True
        return dp[0][0]