# **Leetcode筆記(Interleaving String)**

:::info
:information_source: 題目 : Interleaving String, 類型 : dynamic programming , 等級 : medium
日期 : 2023/07/21，2023/12/06，2023/03/25
:::

### 嘗試
2023/12/06

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

        n, m = len(s1), len(s2)
        dp = [[False] * (m + 1) for _ in range(n + 1)]
        dp[n][m] = True

        for i in range(n, -1, -1):
            for j in range(m, -1, -1):
                # use s1 (i)
                if i < n and dp[i + 1][j] and s1[i] == s3[i + j]:
                    dp[i][j] = True
                # use s2 (j)
                if j < m and dp[i][j + 1] and s2[j] == s3[i + j]:
                    dp[i][j] = True

        return dp[0][0]

2023/03/25
記得是分兩種情況去想
在一個dp[i][j]上面，有兩種可能性，繼承下面的並使用行向字母，或是繼承右邊的並使用列向字母

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        n, m = len(s1), len(s2)
        if n + m != len(s3):
            return False
            
        dp = [[False] * (m + 1) for _ in range(n + 1)]
        dp[n][m] = True

        for i in range(n, -1, -1):
            for j in range(m, -1, -1):
                # 兩種情況
                if i + 1 <= n and s3[i + j] == s1[i] and dp[i + 1][j]:
                    dp[i][j] = True
                if j + 1 <= m and s3[i + j] == s2[j] and dp[i][j + 1]:
                    dp[i][j] = True
        
        return dp[0][0]

---
### **優化**

     0  1  2  3  4  5
     d  b  b  c  a
0 a  T  F  F  F  F  F
1 a  T  F  F  F  F  F 
2 b  T  T  T  T  T  F
3 c  F  T  T  F  T  F 
4 c  F  F  T  T  T  T
5    F  F  F  F  F  T

這是s3
0123456789
aadbbcbcac

左邊是s1，是i
上邊是s2，是j

s1[i] == s3[i + j] 意思是如果s[i]和s3的某個字有對到，
而且剛好接在當前j的後面(所以會是i + j)
-> 會有j的原因是因為要接續j繼續排，所以j數值是固定的
dp[i + 1][j] = True 意思是如果上一個(i + 1)s1的字，
已經被走過了(從背後開始走)，且為true
-> 規定要按造順序走，s1和s2都不能跳
-> 所以上一格為true才可走

if i < len(s1) and s1[i] == s3[i + j] and dp[i + 1][j]:
    dp[i][j] = True
if j < len(s2) and s2[j] == s3[i + j] and dp[i][j + 1]:
    dp[i][j] = True

這個解法是使用動態規劃（Dynamic Programming）來判斷字串 s1、s2是否能夠交錯形成 s3。
時間複雜度為 O(m*n)，其中 m 和 n 分別是 s1 和 s2 的長度。
空間複雜度為 O(m*n)，因為使用了一個 m+1 行 n+1 列的二維陣列 dp 來存儲中間計算結果。

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1) + len(s2) != len(s3):
            return False
        m, n = len(s1), len(s2)
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[m][n] = True

        for i in range(m, -1, -1):
            for j in range(n, -1, -1):
                if i < m and s1[i] == s3[i + j] and dp[i + 1][j]:
                    dp[i][j] = True
                if  j < n and s2[j] == s3[i + j] and dp[i][j + 1]:
                    dp[i][j] = True
        
        return dp[0][0]

---

**:warning: 錯誤語法**
:::warning

:::

**:thumbsup:學習**
:::success

:::

**思路**

**講解連結**
https://www.youtube.com/watch?v=3Rw3p9LrgvE&t=728s
Provided by. Neetocde

###### tags: `dynamic programming` `medium` `leetcode`