經典動態規劃題目：Zipper 字符串交織判斷——判斷第三字符串是否由前兩字符串交織形成

問題描述

給定三個字符串 A、B、C，長度分別為 m、n、m+n。判斷 C 是否可以由 A 和 B 的字符保持各自相對順序交織形成。

示例

• A="cat", B="tree", C="tcraete" → Yes (t-c-r-a-e-t-e)
• A="cat", B="tree", C="catrtee" → Yes (c-a-t-r-t-e-e)
• A="cat", B="tree", C="cttaree" → No

動態規劃解法

定義 dp[i][j] 表示 A 的前 i 個字符和 B 的前 j 個字符能否交織形成 C 的前 i+j 個字符。

狀態轉移方程

dp[0][0] = true
dp[i][j] = (dp[i-1][j] && A[i-1] == C[i+j-1]) ||
           (dp[i][j-1] && B[j-1] == C[i+j-1])

邊界條件

• dp[i][0]：僅用 A 的前 i 個匹配 C 的前 i 個。
• dp[0][j]：僅用 B 的前 j 個匹配 C 的前 j 個。

複雜度

• 時間 O(m×n)，空間 O(m×n) 可優化至 O(min(m,n))。
• m, n ≤ 200，極其輕量。

實現要點

• 字符串索引注意偏移：C 的索引為 i+j-1。
• 輸入數據集數 ≤ 1000，總時間毫秒級。

參考資料

詳細講解：Zipper 字符串交織 DP 詳解