97. Interleaving String

Medium

Description

給定三個字串 s1、s2 和 s3，判斷 s3 是否由 s1 和 s2 交錯組成。交錯是指將 s1 和 s2 各自分割後交替拼接（保持原有順序）能形成 s3。

Example:

Input: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbcbcac” Output: true

Intuition#

長度檢查：若 s1.length + s2.length != s3.length，直接回傳 false
dp[i][j] = true 若：
- dp[i-1][j] && s1[i-1] == s3[i+j-1]（從 s1 取一個字元）
- 或 dp[i][j-1] && s2[j-1] == s3[i+j-1]（從 s2 取一個字元）

Approaches#

1: 2D DP Table#

概念: 建立 (m+1) x (n+1) 的布林表格，逐格填寫。
時間複雜度: O(m * n)
空間複雜度: O(m * n)

class Solution {
    fun isInterleave(s1: String, s2: String, s3: String): Boolean {
        val m = s1.length
        val n = s2.length
        if (m + n != s3.length) return false
        val dp = Array(m + 1) { BooleanArray(n + 1) }
        dp[0][0] = true
        for (i in 1..m) dp[i][0] = dp[i - 1][0] && s1[i - 1] == s3[i - 1]
        for (j in 1..n) dp[0][j] = dp[0][j - 1] && s2[j - 1] == s3[j - 1]
        for (i in 1..m) {
            for (j in 1..n) {
                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[m][n]
    }
}

⭐2: 1D DP（空間優化）#

概念: 只保留一行，逐行更新。dp[j] 保留上一行的值。
時間複雜度: O(m * n)
空間複雜度: O(n)

class Solution {
    fun isInterleave(s1: String, s2: String, s3: String): Boolean {
        val m = s1.length
        val n = s2.length
        if (m + n != s3.length) return false
        val dp = BooleanArray(n + 1)
        for (i in 0..m) {
            for (j in 0..n) {
                if (i == 0 && j == 0) {
                    dp[j] = true
                } else if (i == 0) {
                    dp[j] = dp[j - 1] && s2[j - 1] == s3[j - 1]
                } else if (j == 0) {
                    dp[j] = dp[j] && s1[i - 1] == s3[i - 1]
                } else {
                    dp[j] = (dp[j] && s1[i - 1] == s3[i + j - 1]) ||
                            (dp[j - 1] && s2[j - 1] == s3[i + j - 1])
                }
            }
        }
        return dp[n]
    }
}

🔑 Takeaways#

Pattern: 雙字串匹配 DP — dp[i][j] 代表兩個前綴能否滿足某條件
關鍵技巧: 注意 s3 的索引是 i+j-1；先做長度檢查可以快速排除不可能的情況