Longest Common Subsequence
Problem
Given two strings, find the longest common subsequence (LCS). Your code should return the length of LCS.
- Problem link.
Notes
这是个Two Sequence DP问题,定义状态和状态转移方程
state: $$f[i][j]$$表示前i个字符配上前j个字符的LCS的长度
$$function: f[i][j] = f[i-1][j-1] + 1 // a[i-1] == b[j-1]
\\= MAX(f[i-1][j], f[i][j-1]) // a[i-1] != b[j-1]$$
$$intialize: f[i][0] = 0, f[0][j] = 0$$
$$answer: f[a.length()][b.length()]$$
Solution
class Solution {
public:
/**
* @param A, B: Two strings.
* @return: The length of longest common subsequence of A and B.
*/
int longestCommonSubsequence(string A, string B) {
// write your code here
if(A.length() == 0 || B.length()==0) return 0;
int m = A.length();
int n = B.length();
vector<vector<int> > lcs(m+1, vector<int>(n+1,0));
for(int i=1; i<=m; i++) {
for(int j=1; j<=n; j++) {
if(A[i-1] == B[j-1]) {//注意不是比较A[i] and B[j]哦!
lcs[i][j] = lcs[i-1][j-1] + 1;
} else {
lcs[i][j] = max(lcs[i][j-1], lcs[i-1][j]);
}
}
}
return lcs[m][n];
}
};
需要注意的是lcs状态数组是[m+1][n+1]维的
// Time: O(m * n)
// Space: O(min(m, n))
class Solution {
public:
/**
* @param A, B: Two strings.
* @return: The length of longest common subsequence of A and B.
*/
int longestCommonSubsequence(string A, string B) {
if (A.length() < B.length()) {
return longestCommonSubsequence(B, A);
}
// table[i][j] means the longest length of common subsequence
// of A[0 : i] and B[0 : j].
vector<vector<int>> table(2, vector<int>(A.length() + 1, 0));
// if A[i - 1] != B[j - 1]:
// table[i][j] = max(table[i - 1][j], table[i][j - 1])
// if A[i - 1] == B[j - 1]:
// table[i][j] = table[i - 1][j - 1] + 1
for (int i = 1; i < A.length() + 1; ++i) {
for (int j = 1; j < B.length() + 1; ++j) {
if (A[i - 1] != B[j - 1]) {
table[i % 2][j] = max(table[(i - 1) % 2][j],
table[i % 2][j - 1]);
} else {
table[i % 2][j] = table[(i - 1) % 2][j - 1] + 1;
}
}
}
return table[A.length() % 2][B.length()];
}
};