最長共通部分列のJava（再帰的）

Question

私が働いている問題はここにある： http://practiceit.cs.washington.edu/problem/view/cs2/sections/recursivebacktracking/longestCommonSubsequence

基本的に我々は2つの文字列を与えていると我々は最長共通部分列を見つけるように要求されています。私はソリューションをオンラインで検索し、自分のソリューションと比較しました。私のコードにはバグは見つかりませんでした。私はなぜそれがまだ動作しないのだろうかと思います。

コール値が返さ

：ここ

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"

"supercilious先生"、 "おいしい桃" "eciousそれぞれ"

」マーティ "

""、 "ジョー"」、 "ヘレン"" ""

"スージー"、 "" ""

"ACGGTGTCGTGCTA"、 "CGTTCGGCTATCGTACGT" "CGGTTCGTGT"

私のコード私はすべてのテストケースでStackOverFlowを取得しました。

Answer 1

LCSの計算が正しくありません。 LCSでは、文字列の最後から比較が必要です。 2つの文字列の最後の文字が一致した場合、それは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; 
      } 
     } 
    }