LeetCode 交錯字符串：動態規劃解法（空間優化）

題目描述

給定三個字符串 s1、s2、s3，判斷 s3 是否由 s1 和 s2 交錯組成，且保持 s1、s2 中字符相對順序不變。

動態規劃分析

定義 dp[i][j] 表示 s1 前 i 個字符和 s2 前 j 個字符能否交錯組成 s3 前 i+j 個字符。遞推關係：
dp[i][j] = (dp[i-1][j] && s1[i-1]==s3[i+j-1]) || (dp[i][j-1] && s2[j-1]==s3[i+j-1])
初始 dp[0][0]=true。邊界情況處理單獨由一個字符串組成的情況。
觀察到只依賴前一行和當前行左側，可壓縮為一維數組。

一維 DP 代碼 (Python)

class Solution:
    def isInterleave(self, s1, s2, s3):
        m, n, l = len(s1), len(s2), len(s3)
        if m + n != l:
            return False
        dp = [True] * (m + 1)
        for i in range(m):
            dp[i+1] = dp[i] and s1[i] == s3[i]
        for j in range(n):
            dp[0] = dp[0] and s2[j] == s3[j]
            for i in range(m):
                dp[i+1] = (dp[i] and s1[i] == s3[i+j+1]) or \
                          (dp[i+1] and s2[j] == s3[i+j+1])
        return dp[m]

複雜度

• 時間：O(m*n)
• 空間：O(min(m, n))，取較短字符串作為內層循環。