LeetCode 97 交錯字符串：動態規劃判斷 s3 是否由 s1/s2 交錯構成

LeetCode 97 交錯字符串：動態規劃判斷 s3 是否由 s1/s2 交錯構成

給定 s1, s2, s3，判斷 s3 是否可由 s1 和 s2 交錯構成（保持各自相對順序）。例：s1="aabcc", s2="dbbca", s3="aadbbcbcac" → true。

DP 定義

dp[i][j]：s1[0..i-1] 和 s2[0..j-1] 能否交錯構成 s3[0..i+j-1]。

狀態轉移

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[i][0] = dp[i-1][0] && s1[i-1]==s3[i-1]
• dp[0][j] = dp[0][j-1] && s2[j-1]==s3[j-1]

代碼實現

bool isInterleave(string s1, string s2, string s3) {
    int n1 = s1.size(), n2 = s2.size(), n3 = s3.size();
    if (n1 + n2 != n3) return false;
    
    vector<vector<bool>> dp(n1+1, vector<bool>(n2+1, false));
    dp[0][0] = true;
    for (int i = 1; i <= n1; i++) dp[i][0] = dp[i-1][0] && s1[i-1]==s3[i-1];
    for (int j = 1; j <= n2; j++) dp[0][j] = dp[0][j-1] && s2[j-1]==s3[j-1];
    
    for (int i = 1; i <= n1; i++)
        for (int j = 1; j <= n2; 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]);
    
    return dp[n1][n2];
}

空間優化

滾動數組 dp[j]（一維），逆序或正序更新均可，空間 O(min(n1,n2))。

複雜度

時間 O(n1×n2)，空間 O(n1×n2) 或 O(min(n1,n2))。