題目網址：https://leetcode.cn/problems/longest-common-subsequence/

題意：給兩 string text1、text2, 返回最長共同 subsequence 的長度。若不存在最長共同 subsequence, 則返回 0。

注意：

  • substring 指的是 string 中連續的 subset
  • subsequence 則是 string 的 subset
  • text1、text2 只由小寫字母所組成

Solution 1：

想法：利用 DP

1. 定義狀態：

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

2. 得到轉移方程：

令 text1[1:i] = XXXXi, text2[1:j] = YYYj

  • 若 text1[i] == text2[j], 則 [XXXX]、[YYY] 之 LCS 再加上 text1[i] 即可
    ➔ dp[i][j] = dp[i - 1][j - 1] + 1

  • 否則, LCS 為以下兩種中取較大者

    • [XXXXi]、[YYY]：dp[i][j - 1]
    • [XXXX]、[YYYj]：dp[i - 1][j]

    ➔ dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])

3. 初始化：

  • dp[0][0]：當 text1、text2 皆為 "" 時, LCS 必為 ""
    ➔ dp[0][0] = 0
  • dp[i][0]：當 text2 為 "" 時, LCS 必為 ""
    ➔ dp[i][0] = 0
  • dp[0][j]：當 text1 為 "" 時, LCS 必為 ""
    ➔ dp[0][j] = 0
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        const int m = text1.size(), n = text2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        text1 = '#' + text1;
        text2 = '#' + text2;

        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (text1[i] == text2[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }

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

Solution 2：

想法：同 Solution 1, 發現其實計算 dp[i][j] 只需用到當前列的 dp[i][j - 1] 和上一列的 dp[i - 1][j], 因此只需紀錄當前列和上一列的計算結果即可, 而不用紀錄整個 m x n matrix, 這樣就能將 $O(m \cdot n)$ space 降至 $O(n)$ space

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        const int m = text1.size(), n = text2.size();

        // 讓 n 為較短的 string 長度
        if (n > m) {
            return longestCommonSubsequence(text2, text1);
        }

        vector<int> dp(n + 1, 0);

        text1 = '#' + text1;
        text2 = '#' + text2;

        for (int i = 1; i <= m; ++i) {
            vector<int> nextRow = dp;

            for (int j = 1; j <= n; ++j) {
                if (text1[i] == text2[j]) {
                    nextRow[j] = dp[j - 1] + 1;
                } else {
                    nextRow[j] = max(nextRow[j - 1], dp[j]);
                }
            }

            dp = move(nextRow); // 更新 dp, 下一輪中這輪所計算的會變成上一輪
        }

        return dp.back();
    }
};
  • time：$O(m \cdot n)$ ➔ for loop
  • space：$O(min(m, n))$ ➔ dp, nextRow