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

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]; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。