97. Interleaving String

- 2 minutes read - 702 words

Leetcode 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];
};