1143. Longest Common Subsequence ---M~~~~~

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

 

Example 1:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

 

Constraints:

• 1 <= text1.length, text2.length <= 1000
• text1 and text2 consist of only lowercase English characters.

 

A:

二维 DP

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n1 = text1.length();
        int n2 = text2.length();
        vector<vector<int>> DP(n1+1, vector<int>(n2+1,0));
        for(int i =0;i<n1;i++){
            char ch1 = text1[i];
            for(int j =0;j<n2;j++){
                if(ch1==text2[j]){
                    DP[i+1][j+1] = DP[i][j] + 1;
                }else{
                    DP[i+1][j+1] = max(DP[i+1][j], DP[i][j+1]);
                }
            }
        }
        return DP[n1][n2];        
    }
};

转换成 一维  (memory usage beat 78%)

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n1 = text1.length(), n2 = text2.length();
        vector<int> dp(n1 + 1, 0);
        for (auto ch : text2) {
            vector<int> dp2(n1 + 1, 0);
            for (int i = 1; i <= n1; i++) {
                if (text1[i - 1] == ch) {
                    dp2[i] = 1 + dp[i - 1];
                } else {
                    dp2[i] = max(dp2[i - 1],
                                 dp[i]); // choose betwen the left and upper
                }
            }
            dp = dp2;
        }
        return dp[n1];
    }
};

进一步的修改，就是不每次生成一个空间。而是reuse the DP space (memory usage beat 93%)

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {        
        int n1 = text1.length();
        int n2 = text2.length();
        vector<vector<int>> DP(2, vector<int>(n2+1, 0));
        for(int i= 1;i<=n1;i++){
            char ch1 = text1[i-1];
            for(int j=1;j<=n2;j++){
                if(ch1 == text2[j-1]){
                    DP[i%2][j] = DP[(i-1)%2][j-1] + 1;
                }else{
                    DP[i%2][j] = max(DP[i%2][j-1], DP[(i-1)%2][j] );
                }
            }
        }
        return DP[n1%2][n2];
    }
};

然而，空间复杂度还是 O (n1+ n2)

考虑转换成 O(1)  的空间

？？？？可以吗？ 我还不太会