97. Interleaving String
- 2 minutes read - 702 wordsLeetcode 97. Interleaving String
題目
Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.
An interleaving of two strings s and t is a configuration where they are divided into non-empty substrings such that:
- s = s1 + s2 + … + sn
- t = t1 + t2 + … + tm
- |n - m| <= 1
- The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + … or t1 + s1 + t2 + s2 + t3 + s3 + …
Note: a + b is the concatenation of strings a and b.
想法
一開始在看這題的時候用遞迴寫,結果 TLE。
所以改成用動態規劃來做。
我們會需要一個長為 m + 1 寬為 n + 1 的二維 DP 陣列。
DP[a][b] = (true | false)
意義:在取 s1 前 a 個字與 s2 前 b 個字的時候是否還合法。
初始狀態當然就是 a = b = 0 的時候一定合法。
接著先做單純 s1 及單純 s2 的狀態轉移。
接著再進行兩字串混合的狀態轉移。
最後看取兩完整的 s1 與 s2 時是否還合法就可以了。
實作
Javascript
/**
* @param {string} s1
* @param {string} s2
* @param {string} s3
* @return {boolean}
*/
var isInterleave = function(s1, s2, s3) {
let m = s1.length, n = s2.length;
// 長度不合的話直接 false
if(m + n !== s3.length) return false;
// DP 陣列,初始值為 false
let dp = [];
for(let i = 0; i <= m; i++) {
let row = [];
for(let j = 0; j <= n; j++) row.push(false);
dp.push(row);
}
// 代表 m, n 皆為 0 的話,結果是 true 的狀態
dp[0][0] = true;
// 對 s2 長度為 0 時,單純只有 s1 進行狀態轉移
for(let i = 1; i <= m; i++) {
// 如果長度為 i - 1 時合法,且兩者第 i 個字元相同,長度為 i 也合法
dp[i][0] = dp[i - 1][0] && s3[i - 1] === s1[i - 1];
}
// 對 s1 長度為 0 時,單純只有 s2 進行狀態轉移
for(let j = 1; j <= n; j++) {
// 如果長度為 j - 1 時合法,且兩者第 j 個字元相同,長度為 j 也合法
dp[0][j] = dp[0][j - 1] && s3[j - 1] === s2[j - 1];
}
// 就 DP 陣列中間剩餘部分進行狀態轉移
for(let i = 1; i <= m; i++) {
for(let j = 1; j <= n; j++) {
// 取 s1 前 i - 1 個、s2 前 j 個時合法,那麼只要 s3 的第 i + j 個字元與 s1 的第 i 個字元相同就合法
// 或者,取 s1 前 i 個、s2 前 j - 1 個時合法,那麼只要 s3 的第 i + j 個字元與 s2 的第 j 個字元相同就合法
dp[i][j] = (dp[i - 1][j] && s3[i - 1 + j] === s1[i - 1]) || (dp[i][j - 1] && s3[j - 1 + i] === s2[j - 1]);
}
}
// 回傳建構完的 DP 終點
return dp[m][n];
};