97. Interleaving String

題目網址：https://leetcode.cn/problems/interleaving-string/

題意：給三個 string s1、s2、s3, 返回 s3 是否是由 s1 和 s2 交錯組成的。

兩個 sting s、t 交錯的定義與過程如下, 其中每個 string 都會被分割成若干個 non-empty substring：

• s = s1 + s2 + ... + sn
• t = t1 + t2 + ... + tm
• |n - m| <= 1
• 交錯是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或 t1 + s1 + t2 + s2 + t3 + s3 + ...

注意：a + b 代表 string a 和 b 串接。

Solution：

想法：利用 DP, 其中 dp[i][j] 表示 s1 前 i 個 char 和 s2 前 j 個 char 能否構成 s3 前 i + j 個 char

dp[i][j] 為 true 有兩種情況：

• s1[i - 1] == s3[i + j - 1] && dp[i - 1][j]
  • 當 s1 的最後一個 char 等於 s3 最後一個 char
  • 且 s1 前 i - 1 個 char、s2 前 j 個 char 能構成 s3 前 i + j - 1 個 char
• s2[j - 1] == s3[i + j - 1] && dp[i][j - 1]
  • 當 s2 的最後一個 char 等於 s3 最後一個 char
  • 且 s1 前 i 個 char、s2 前 j - 1 個 char 能構成 s3 前 i + j - 1 個 char

滿足上面公式的 i、j 必須 ≥ 1, 否則 dp[i - 1][j]、dp[i][j - 1] 會越界

也就是說 dp[i][j] 只考慮了 i, j ≥ 1 的情況, 並沒有考慮到：

• i = 0, j = 0 : 也就是 s1、s2 皆為 "" 時, 能否組成 s3 = ""
• i = 0 ~ m, j = 0 : 也就是 s2 為 "" 時, 僅靠 s1 能否構成 s3
• i = 0, j = 0 ~ n : 也就是 s1 為 "" 時, 僅靠 s2 能否構成 s3

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        const int m = s1.size(), n = s2.size();

        if (m + n != s3.size()) {
            return false;
        }

        // m + 1、n + 1 是因為要考慮 s1、s2 為空的情況
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        dp[0][0] = true; // 當 s1、s2 皆為 "" 時, 能構成 s3 = ""

        // s2 皆為 "" 時, 僅靠 s1 能否構成 s3
        for (int i = 1; i <= m; ++i) {
            dp[i][0] = (s1[i - 1] == s3[i - 1]) && dp[i - 1][0];
        }

        // s1 皆為 "" 時, 僅靠 s2 能否構成 s3
        for (int j = 1; j <= n; ++j) {
            dp[0][j] = (s2[j - 1] == s3[j - 1]) && dp[0][j - 1];
        }

        // i, j 皆 ≥ 1 的狀態轉移
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                dp[i][j] = (s1[i - 1] == s3[i + j - 1] && dp[i - 1][j]) ||
                           (s2[j - 1] == s3[i + j - 1] && dp[i][j - 1]);
            }
        }

        return dp[m][n];
    }
};

• time：$O(m \cdot n)$ ➔ for loop
• space：$O(m \cdot n)$ ➔ dp