最长公共子序列的Java（递归）

Question

我工作的问题是在这里： 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”

“她卖”， “海贝”， “sesells”

“12345”， “54321 21 54321”， “123”

“白眼教师”， “美味的桃子”， “ecious每个”

“君子好逑”， “海伦” “”

“”， “乔” “”

“苏茜”， “”， “”

“ACGGTGTCGTGCTA”， “CGTTCGGCTATCGTACGT” “CGGTTCGTGT”

用我的代码我得到了所有测试用例的StackOverFlow。

Answer 1

您的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; 
      } 
     } 
    }