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

Given two strings text1 and text2, return the length of their longest common subsequence.

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. (eg, "ace" is a subsequence of "abcde" while "aec" is not). A common subsequence of two strings is a subsequence that is common to both strings.

 

If there is no common subsequence, return 0.

 

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 <= 1000
• 1 <= text2.length <= 1000
• The input strings consist of lowercase English characters only.

 

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 68%)

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

进一步的修改，就是不每次生成一个空间。而是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)  的空间

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