最近刚好算法试验做了这个, 水一篇博客吧
算法思路
根本剖析:
假如字符串A的长度为m, 字符串B的长度为n, 应用一个数组fm示意对应后果, 其中f[i][j]示意 A.substr(0, i) 和 B.substr(0, j)这两个子字符串的LCS.
思考f[i][j], 他总是能够从上方⬆ (即不应用A的第i个字符)和 左方⬅(不应用B的第j个字符)两个方向转移过去, 因而有f[i][j] = max(f[i – 1][j], f[i][j – 1]);
此外, 如果A[i] == B[j], 那么它能够从左上方转移过去, 此时有f[i][j] = max(f[i][j], f[i – 1][j – 1] + 1);
空间优化:
上述剖析曾经能够残缺地解决LCS问题, 想求出LCS只须要在转移的时候进行记录就行, 不过空间复杂度是O(mn)的, 而后通过咱们的剖析过程能够看到, 转移的时候只波及了以后行和上一行(这里假如行size更小, 如果列size更小的话同理).
因而咱们能够用两个长度为m + 1的数组, 通过不停更新来实现这个算法.
空间进一步优化:
通过上一步优化之后所用空间为两个长度为 m + 1的数组, 以及常数个额定变量. 不过还能够更进一步优化, 因为从头至尾咱们转移到[i][j]的时候只和三个地位的值无关: 正上方[i – 1][j], 左方[i][j – 1]和左上方[i – 1][j – 1].
因而咱们能够思考用一个数组来示意, 在只应用一个数组的状况下, 更新前f[j]就是上一轮更新后的上方f[i – 1][j], 而f[j – 1]也就是左方f[i][j – 1], 也就是说咱们在更新f[j]的时候, 须要的三个值中的两个都在这个数组中了, 那么咱们只须要缓存f[i – 1][j – 1]就行了. 这种状况下, 空间为一个长度为m + 1的数组, 加上两个额定变量. 空间复杂度较低.
代码
奢侈:
class Solution {public: int longestCommonSubsequence(string text1, string text2) { int n1 = text1.size(), n2 = text2.size(); vector<vector<int>> dp(n1 + 1, vector<int> (n2 + 1, 0)); for (int i = 1; i <= n1; ++i) { for (int j = 1; j <= n2; ++j) { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); // 从正上方和左方转移 if (text1[i - 1] == text2[j - 1]) { dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1); // 从斜上方转移 } } } return dp[n1][n2]; }};两个数组:
class Solution {public: int longestCommonSubsequence(string text1, string text2) { int n1 = text1.size(), n2 = text2.size(); int minlen = min(n1, n2), maxlen =max(n1, n2); // 应用较小的长度作为数组长度 vector<int> pre(minlen + 1, 0); vector<int> cur(minlen + 1, 0); for (int i = 1; i <= maxlen; ++i) { for (int j = 1; j <= minlen; ++j) { cur[j] = max(cur[j - 1], pre[j]); // 从上方和左方转移 // 从左上方转移 if (n1 > n2 && text1[i - 1] == text2[j - 1]) { cur[j] = max(cur[j], pre[j - 1] + 1); } if (n1 <= n2 && text2[i - 1] == text1[j - 1]) { cur[j] = max(cur[j], pre[j - 1] + 1); } } // 更新pre for (int j = 1; j <= minlen; ++j) { pre[j] = cur[j]; } } return cur[minlen]; }};一个数组:
class Solution {public: int longestCommonSubsequence(string text1, string text2) { int n1 = text1.size(), n2 = text2.size(); int minlen = min(n1, n2), maxlen = max(n1, n2); vector<int> cur(minlen + 1, 0); // 应用一个数组实现 for (int i = 1; i <= maxlen; ++i) { int pre = 0; for (int j = 1; j <= minlen; ++j) { int nextPre = cur[j]; cur[j] = max(cur[j - 1], cur[j]); // 从上方和左方转移, 自身就是上方 // 从左上方转移 if (n1 > n2 && text1[i - 1] == text2[j - 1]) { cur[j] = max(cur[j], pre + 1); } if (n1 <= n2 && text2[i - 1] == text1[j - 1]) { cur[j] = max(cur[j], pre + 1); } // 更新f[i - 1][j - 1] pre = nextPre; } } return cur[minlen]; }};