1143. Longest Common Subsequence

這題是一個標準的dp, 我們會分析以下四種case

i ==0 && j ==0
我們只需判斷第一個字是否相同
i == 0&& j!=0
就是跟j -1做比較, 若j-1已經是1了, 在相同也沒用因為只跟i的第一個字母比,但如果j-1不是1,這邊就要變成1
i != 0 && j == 0
跟上面同, ij互換而已
i!=0 && j != 0
如果s[i] == s[j], 那就是s[i-1][j -1] + 1
不同 就是 max(s[i-1][j] , s[i][j-1])

以下可以寫成

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size();
        int n = text2.size();
        vector<vector<int>> dp(m, vector<int>(n , 0));
        for(int i = 0; i < m;i++){
            for(int j = 0;j < n;j++){
                if(i == 0 && j == 0){
                    if(text1[i] == text2[j]){
                        dp[i][j] = 1;
                    }
                }else if (i == 0 && j != 0){
                     if(text1[i] == text2[j]){
                        dp[i][j] = max(dp[i][j -1], 1);
                     }else{
                         dp[i][j] = dp[i][j -1];
                     }
                }else if ( i != 0 && j == 0){
                    if(text1[i] == text2[j]){
                        dp[i][j] =  max(dp[i -1][j], 1);
                    }else{
                        dp[i][j] = dp[i - 1][j];
                    }
                }else{
                    if(text1[i] == text2[j]){
                        dp[i][j] = dp[i-1][j-1] + 1;
                    }else{
                        dp[i][j] = max(dp[i -1][j] , dp[i][j -1]);
                    }
                }
            }
        }
        return dp[m-1][n-1];
    }
};

為什麼要拉0出來判斷, 因為0 -1 會超界

這邊還有一個疑問, 為什麼是dp[i][j] = max(dp[i -1][j] , dp[i][j -1])

我們建立一張表

假設text1是ace, 他在 建立 [2, 3]的時候, 如果直接參考[1, 3]就會參考錯誤, 應該是要參考[2, 2]

網路上查到一個多一個空間,然後從1, 走到長度為m(記得 不是m-1) 精簡的做法

class Solution {
public:
  int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size();
    int n = text2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= n; j++) {
        if (text1[i - 1] == text2[j -1]) {
          dp[i][j] = dp[i - 1][j - 1] + 1;
        } else {
          dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
      }
    }
    return dp[m][n];
  }
};