LeetCode 97 Interleaving String：二維 DP 判斷交錯字符串

LeetCode 97 Interleaving String：二維 DP 判斷交錯字符串

題目大意：給定 s1、s2、s3，判斷 s3 是否由 s1 和 s2 交錯構成（保持各自字符相對順序）。長度均 ≤ 100。

DP 定義與轉移

f[i][j] = s1 前 i 字符、s2 前 j 字符能否交錯構成 s3 前 i+j 字符。
初始化：

• f[0][0] = true
• f[i][0] = f[i-1][0] && (s1[i-1] == s3[i-1])（僅用 s1）
• f[0][j] = f[0][j-1] && (s2[j-1] == s3[j-1])（僅用 s2）

代碼實現（Java）

public boolean isInterleave(String s1, String s2, String s3) {
    if (s1.length()+s2.length() != s3.length()) return false;
    boolean[][] f = new boolean[s1.length()+1][s2.length()+1];
    f[0][0] = true;
    for (int i=1; i<=s1.length(); ++i) f[i][0] = f[i-1][0] && s1.charAt(i-1)==s3.charAt(i-1);
    for (int j=1; j<=s2.length(); ++j) f[0][j] = f[0][j-1] && s2.charAt(j-1)==s3.charAt(j-1);
    for (int i=1; i<=s1.length(); ++i)
        for (int j=1; j<=s2.length(); ++j)
            f[i][j] = (f[i-1][j] && s1.charAt(i-1)==s3.charAt(i+j-1))
                   || (f[i][j-1] && s2.charAt(j-1)==s3.charAt(i+j-1));
    return f[s1.length()][s2.length()];
}

優化：滾動數組

只依賴上一行，可用 boolean[] dp = new boolean[s2.length()+1] 從左向右更新，空間 O(min(n,m))。

複雜度

時間 O(n×m)，空間 O(n×m)（或 O(min(n,m))）。n,m ≤ 100 極快。

總結

二維 DP 經典模板：雙序列交錯構成第三序列。狀態定義雙索引，轉移雙來源。初始化邊界條件是關鍵。滾動數組優化空間後代碼更優雅。同類題目：LeetCode 72 Edit Distance、583 Delete Operation 等。