java - 最長共通サブシーケンス 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」

「彼女は売る」、「貝殻」、「貝殻」

"12345"、"54321 21 54321" "123"

「やんちゃ先生」「おいしいもも」「えちえちえちえち」

「マーティ」「ヘレン」「」

""、"ジョー" ""

「スージー」「」「」

「ACGGTGTCGTGCTA」、「CGTTCGGCTATCGTACGT」「CGGTTCGTGT」

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