首页 > 代码库 > Longest Common Subsequence
Longest Common Subsequence
Problem statement:
Given two strings, find the longest common subsequence (LCS).
Your code should return the length of LCS.
Have you met this question in a real interview?
Yes
Clarification
What‘s the definition of Longest Common Subsequence?
- https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
- http://baike.baidu.com/view/2020307.htm
Example
For "ABCD" and "EDCA", the LCS is "A" (or "D", "C"), return 1.
For "ABCD" and "EACB", the LCS is "AC", return 2.
Solution:
This is a DP problem for two sequences. Such as 72. Edit Distance and 583. Delete Operation for Two Strings.
The key points is also dp[i][j] means the LCS of first i chars in A and first j char in B, and return dp[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) { // write your code here int m = A.size(); int n = B.size(); 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]; }};
Longest Common Subsequence
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。