我正在开发一个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/

10-14 13:38
查看更多