給定三個字串
s1、s2和s3，判斷s3是否由s1和s2交錯組成。交錯是指將s1和s2各自分割後交替拼接（保持原有順序）能形成s3。
Example:
Input: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbcbcac” Output: true
Intuition
TIP
dp[i][j] 表示 s1 前 i 個字元和 s2 前 j 個字元能否交錯組成 s3 的前 i+j 個字元。
- 長度檢查：若
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 — O(m * n) / O(m * n)
- Idea: 建立
(m+1) x (n+1)的布林表格，逐格填寫。 - Time:
O(m * n) - Space:
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 (Space Optimized) — O(m * n) / O(n)
- Idea: 只保留一行，逐行更新。
dp[j]保留上一行的值。 - Time:
O(m * n) - Space:
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]代表兩個前綴能否滿足某條件 - Key trick: 注意 s3 的索引是
i+j-1；先做長度檢查可以快速排除不可能的情況