领扣LintCode算法问题答案-77. 最长公共子序列
目录
77. 最长公共子序列描述样例 1：样例 2：
题解鸣谢
77. 最长公共子序列
描述
给出两个字符串，找到最长公共子序列(LCS)，返回LCS的长度。
最长公共子序列的定义：
最长公共子序列问题是在一组序列（通常2个）中找到最长公共子序列（注意：不同于子串，LCS不需要是连续的子串）。该问题是典型的计算机科学问题，是文件差异比较程序的基础，在生物信息学中也有所应用。
样例 1：
输入: "ABCD" and "EDCA"
输出: 1
解释:
LCS 是 'A' 或 'D' 或 'C'
样例 2：
输入: "ABCD" and "EACB"
输出: 2
解释:
LCS 是 "AC"
题解
public class Solution {
public int longestCommonSubsequence(String A
, String B
) {
if (A
.length() == 0
|| B
.length() == 0) {
return 0;
}
int[][] dp
= new int[A
.length() + 1][B
.length() + 1];
for (int i
= 1; i
<= A
.length(); i
++) {
for (int j
= 1; j
<= B
.length(); j
++) {
if (A
.charAt(i
- 1) == B
.charAt(j
- 1)) {
dp
[i
][j
] = dp
[i
- 1][j
- 1] + 1;
} else {
dp
[i
][j
] = Math
.max(dp
[i
- 1][j
], dp
[i
][j
- 1]);
}
}
}
return dp
[A
.length()][B
.length()];
}
}
原题链接点这里
鸣谢
非常感谢你愿意花时间阅读本文章，本人水平有限，如果有什么说的不对的地方，请指正。 欢迎各位留言讨论，希望小伙伴们都能每天进步一点点。
