LeetCode——1143.最长公共子序列【LCS 标准代码、空间压缩】

题解

• 标准的LCS，两套代码，一套标准LCS，一套空间压缩
• 标准代码可以直接通过b数组逆推路径

AC-Code

• 标准LCS

class Solution {
    
public:int longestCommonSubsequence(string text1, string text2) {
    int len1 = text1.length();int len2 = text2.length();int** dp = new int* [len1 + 1];for (int i = 0; i <= len1; ++i) {
    dp[i] = new int[len2 + 1];memset(dp[i], 0, sizeof(int) * (len2 + 1));}/*int** b = new int* [len1 + 1];for (int i = 0; i <= len1; ++i) {b[i] = new int[len2 + 1];memset(b[i], 0, sizeof(int) * (len2 + 1));}*/for (int i = 1; i <= len1; ++i) {
    for (int j = 1; j <= len2; ++j) {
    if (text1[i - 1] == text2[j - 1]) {
    dp[i][j] = dp[i - 1][j - 1] + 1;// b[i][j] = 1; // 左上}else if (dp[i - 1][j] >= dp[i][j - 1]) {
    dp[i][j] = dp[i - 1][j];// b[i][j] = 3; // 上}else {
    dp[i][j] = dp[i][j - 1];// b[i][j] = 2; // 左}}}return dp[len1][len2];}
};

• 空间压缩

class Solution {
    
public:int longestCommonSubsequence(string text1, string text2) {
    int len1 = text1.length();int len2 = text2.length();int *dp = new int[len2 + 1];memset(dp, 0, sizeof(int) * (len2 + 1));for(int i = 1; i <= len1; ++i){
    int last = 0;   // dp[i - 1][j - 1]for(int j = 1; j <= len2; ++j){
    int temp = dp[j];   // dp[i - 1][j]if(text1[i - 1] == text2[j - 1])    dp[j] = last + 1;   // 改完后,dp[j]表示dp[i][j]else    dp[j] = max(dp[j - 1], dp[j]);last = temp;    // 每次更新last，确保在下一次迭代时，last指向的是那个状态的dp[i - 1][j - 1]}}return dp[len2];}
};