交错字符串（Interleaving String）

解題思路

本題採用動態規劃（Dynamic Programming）解決交錯字串問題。首先進行邊界檢查，若 s1 與 s2 的長度總和不等於 s3 的長度，直接回傳 False。接著建立一個 (l1+1) x (l2+1) 的布林矩陣 dp，其中 dp[i][j] 表示 s1 的前 i 個字元與 s2 的前 j 個字元能否交錯組成 s3 的前 i+j 個字元。初始化 dp[0][0] 為 True，並分別計算第一列與第一行的邊界情況（即僅由 s1 或僅由 s2 組成的情況）。在填表過程中，dp[i][j] 的狀態轉移取決於兩種情況：若 s2 的第 j 個字元與 s3 的當前字元匹配，且 dp[i][j-1] 為真；或若 s1 的第 i 個字元與 s3 的當前字元匹配，且 dp[i-1][j] 為真。最終 dp[l1][l2] 即為答案。

通過的程式碼

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        l1 = len(s1)
        l2 = len(s2)
        l3 = len(s3)

        if l1 + l2 != l3:
            return False
        dp = [[False] * (l2+1) for i in range(l1+1)]
        dp[0][0] = True

        for i in range(1, l1+1):
            dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1]
        for i in range(1, l2+1):
            dp[0][i] = dp[0][i-1] and s2[i-1] == s3[i-1]

        for i in range(1, l1+1):
            for j in range(1, l2+1):
                dp[i][j] = (dp[i][j-1] and s2[j-1] == s3[i+j-1] ) or ( dp[i-1][j] and s1[i-1]==s3[i+j-1])
        return dp[-1][-1]