我正在研究的问题在这里：
http://practiceit.cs.washington.edu/problem/view/cs2/sections/recursivebacktracking/longestCommonSubsequence
基本上，我们给了两个字符串，并要求我们找到最长的公共子序列。我在线搜索了解决方案，并将它们与自己的解决方案进行了比较，但是我的代码中找不到任何错误。我不知道为什么它仍然行不通。
另外，还要求我使用递归方法解决此问题
这是我的代码：
public static String longestCommonSubsequence(String a, String b){
if(a.isEmpty() || b.isEmpty()){
return "";
}
if (a.substring(a.length() - 1).equals(b.substring(b.length() - 1))){
return longestCommonSubsequence(a.substring(0, a.length() - 1), b.substring(0, b.length()
- 1)) + a.substring(a.length() - 1);
} else {
String first = longestCommonSubsequence(a, b.substring(b.length() - 1));
String second = longestCommonSubsequence(a.substring(a.length() - 1), b);
if(first.length() > second.length()){
return first;
}
return second;
}
}
这是所有测试用例：
收回通话价值
“ ABCDEFG”，“ BGCEHAF”“ BCEF”
“她卖”，“贝壳”，“卖”
“ 12345”，“ 54321 21 54321”“ 123”
“卑鄙的老师”，“美味的桃子”，“珍贵的每个”
“ Marty”，“ Helene”“”
“”，“乔”“”
“ Suzy”，“”“”
“ ACGGTGTCGTGCTA”，“ CGTTCGGCTATCGTACGT”，“ CGGTTCGTGT”
用我的代码，我得到了所有测试用例的StackOverFlow。
最佳答案
您的LCS计算不正确。在LCS中，您需要从字符串末尾进行比较。如果两个字符串的最后一个字符匹配，则表示它是LCS的一部分。
public static String longestCommonSubsequence(String a, String b) {
int alength = a.length() - 1;
int blength = b.length() - 1;
if (alength < 0 || blength < 0)
return "";
if (a.substring(alength).equals(b.substring(blength))) {
return longestCommonSubsequence(a.substring(0, alength), b.substring(0, blength))
+ a.substring(alength);
} else {
String first = longestCommonSubsequence(a, b.substring(0, blength));
String second = longestCommonSubsequence(a.substring(0, alength), b);
if (first.length() > second.length()) {
return first;
} else {
return second;
}
}
}