題目網址：https://leetcode.cn/problems/shortest-common-supersequence/

題意：給兩 string str1 和 str2, 返回同時以 str1 和 str2 作為 subsequence 的最短 string。如果答案不止一個, 則返回滿足條件的任意一個答案。

如果從 string T 中刪除一些char（也可能不刪除, 並且選出的這些 char 可以位於 T 中的任意位置）, 可以得到 string S, 那麼 S 就是 T 的subsequence）

注意：str1、str2 皆由小寫字母所組成。

Solution：

想法：利用 DP

1. 定義狀態：

  • 首先, 會在 str1、str2 前先加上一個 #, 代表什麼元素都沒有的狀態
  • dp[i][j]：str1[1:i]、str2[1:j] 的 SCS 之長度

2. 得到轉移方程：

  • 若 str1[i] == str2[j]：此時的 SCS 為原先的 SCS 加上 str1[i] 即可
    ➔ dp[i][j] = dp[i - 1][j - 1] + 1
  • 否則, 此時的 SCS 為原先的 SCS 加上 str1[i] 或 str2[j]
    ➔ dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1

3. 初始化：

  • dp[0][0]：兩個空 "" 的 SCS 為 ""
  • dp[i][0]：str1[1:i] 和 "" 的 SCS 為 str1[1:i]
    ➔ dp[i][0] = i, 其中 1 ≤ i ≤ m
  • dp[0][j]："" 和 str2[1:j] 的 SCS 為 str2[1:j]
    ➔ dp[0][j] = j, 其中 1 ≤ j ≤ n

最後, 再從 str1、str2、dp 由後往前回推, 以構建出 SCS

class Solution {
public:
    string shortestCommonSupersequence(string str1, string str2) {
        const int m = str1.size(), n = str2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        str1 = '#' + str1;
        str2 = '#' + str2;

        for (int i = 1; i <= m; ++i) {
            dp[i][0] = i;
        }

        for (int j = 1; j <= n; ++j) {
            dp[0][j] = j;
        }

        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (str1[i] == str2[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
                }
            }
        }

        int i = m, j = n;
        string res;

        while (i > 0 && j > 0) {
            if (str1[i] == str2[j]) {
                res += str1[i];
                --i;
                --j;
            } else if (dp[i][j] == dp[i - 1][j] + 1) {
                res += str1[i];
                --i;
            } else {
                res += str2[j];
                --j;
            }
        }

        while (i > 0) {
            res += str1[i--];
        }

        while (j > 0) {
            res += str2[j--];
        }

        reverse(res.begin(), res.end()); // 從後面回推 SCS, 故要 reverse

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