我正在开发一个JavaScript应用程序,并且需要一种用于最长公共子序列的递归算法,因此我尝试了here并进行了尝试。
它是这样的:
function lcs(a, b) {
var aSub = a.substr(0, a.length - 1);
var bSub = b.substr(0, b.length - 1);
if (a.length === 0 || b.length === 0) {
return '';
} else if (a.charAt(a.length - 1) === b.charAt(b.length - 1)) {
return lcs(aSub, bSub) + a.charAt(a.length - 1);
} else {
var x = lcs(a, bSub);
var y = lcs(aSub, b);
return (x.length > y.length) ? x : y;
}
}
我到目前为止尝试过的几个测试用例都能正常工作,但是我发现它在以下测试用例上循环:
答:此实体正常
b:这行不通,但应该
它还循环与:
答:此实体正常
b:效果不佳
在某个时候应该进入中间分支。
我注意到它是相同算法的Java版本(here)的翻译。它是这样的:
public static String lcs(String a, String b){
int aLen = a.length();
int bLen = b.length();
if(aLen == 0 || bLen == 0){
return "";
}else if(a.charAt(aLen-1) == b.charAt(bLen-1)){
return lcs(a.substring(0,aLen-1),b.substring(0,bLen-1))
+ a.charAt(aLen-1);
}else{
String x = lcs(a, b.substring(0,bLen-1));
String y = lcs(a.substring(0,aLen-1), b);
return (x.length() > y.length()) ? x : y;
}
}
我假设String.substr()和String.substring()相同(不是),就认为JavaScript翻译是错误的。
为确保不是这种情况,我在相同的测试用例here上尝试了Java。
你猜怎么了? Java版本也不会结束。
我正在调试它,因为它是递归的。
有人对它出了什么问题有任何想法吗?
最佳答案
正如其他人在评论中指出的那样,该程序本身是正确的。您遇到的问题是由于在此实现中,代码具有指数级的时间复杂度,因此花很长时间才能运行示例输入。如果您让它长时间运行,它将返回正确的结果。
正如其他人在评论中也指出的那样,使用动态编程可以解决两个字符串之间的LCS,并降低了时间复杂度,这将更快地解决它。有关更多帮助(wikipedia),请参考Internet,或者更好的办法是自己解决这个问题,考虑到以下事实:对于每个长度为n的字符串,恰好有N ^ 2个子字符串。您只需检查b中是否存在a的任何子字符串,就可以用N ^ 2 * M ^ 2(n m是两个字符串的长度)简单地解决它。问自己是否可以做得更好?如果是,如何,如果不是,为什么。
关于javascript - 递归最长公共(public)子序列循环还是永远占用?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/31451451/