Description
Given two strings, find the longest common subsequence (LCS).
Your code should return the length of LCS.
Example 1:
Input: "ABCD" and "EDCA"
Output: 1
Explanation:
LCS is 'A' or 'D' or 'C'
Example 2:
Input: "ABCD" and "EACB"
Output: 2
Explanation:
LCS is "AC"
思路:
这是一个经典的动态规划题,定义dp矩阵,dp[i][j]表示A串匹配到i,B串匹配到j时的最大公共长度。dp有A.length()+1行,有B.length()列。第一行与第一列都为0;
有状态转移方程:
最后返回dp的最大值即为最长公共子串长度,代码如下:
class Solution {
public:
/**
* @param A: A string
* @param B: A string
* @return: The length of longest common subsequence of A and B
*/
int longestCommonSubsequence(string &A, string &B) {
// write your code here
int m = A.size(), n = B.size();
if (m == 0 || n==0) return 0;
//int dp[m+1][n+1];
std::vector<vector<int>> dp(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]) {
dp[i][j] = dp[i-1][j-1] + 1;
}
else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[m][n];
}
};
类似题目:
网友评论