longest common subsequence java (recursive)

Question

The problem I'm working on is here: http://practiceit.cs.washington.edu/problem/view/cs2/sections/recursivebacktracking/longestCommonSubsequence

basically we are given two strings and we are requested to find the longest common subsequence. I've searched for solutions online and compared them to my own solution, and I couldn't find any bugs in my code. I wonder why it still wouldn't work.

And also, I was requested to solve this problem by using recursive methods

Here's my code:

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

And here are all the test cases:

Call Value Returned

"ABCDEFG", "BGCEHAF" "BCEF"

"she sells", "seashells" "sesells"

"12345", "54321 21 54321" "123"

"supercilious teacher", "delicious peach" "ecious each"

"Marty", "Helene" ""

"","Joe" ""

"Suzy", "" ""

"ACGGTGTCGTGCTA", "CGTTCGGCTATCGTACGT" "CGGTTCGTGT"

with my code I got StackOverFlow for all the test cases.

It may work. The advantage of using DP based solution is running time. — Raghav, Nov 22 '16 at 19:48
But the result I get is just an empty string. I tried debugging and noticed that the line `String first = longestCommonSubsequence(a, b.substring(1))` keeps running and cut off the letters from String b until it's empty. And then an empty String is returned. — Amber, Nov 22 '16 at 19:51
Possible duplicate of [How do I compare strings in Java?](http://stackoverflow.com/questions/513832/how-do-i-compare-strings-in-java) — azurefrog, Nov 22 '16 at 19:51
Specifically, `a.substring(0, 1) == b.substring(0, 1)` will always be false. — azurefrog, Nov 22 '16 at 19:52
So I changed "==" into .equals(), it worked for several tests. But apparently there's still something wrong because it's not working for all the tests. — Amber, Nov 22 '16 at 19:59
And lo, the fixing of the bug exposed another bug. Welcome to programming. ;-) — azurefrog, Nov 22 '16 at 20:02
@Amber Your LCS calculation is incorrect. Please see my solution below — Raghav, Nov 22 '16 at 20:08

score 0 · Answer 1 · answered Nov 22 '16 at 20:03

Your LCS calculation is incorrect. In LCS you need compare from the end of the string. If the last characters of two strings match it means, it would be part of your 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;
            }
        }
    }

Thanks for your solution. I edited my code but it still didn't work. Other than that stackflowerror I wanted to ask why checking form the beginning from the strings wouldn't work? — Amber, Nov 22 '16 at 20:16
@Amber you should not get any stackoverflow error in above code. Can you post test case?. Even if you find a match at beginning of a string there is no guarantee that it would be part of your LCS. — Raghav, Nov 22 '16 at 20:24
I've post them. The error appears on line 5 and I couldn't think of the reason. — Amber, Nov 22 '16 at 20:38

score 0 · Answer 2 · edited Jan 26 '21 at 21:52

You should change a.substring() to a.charAt()

public static String LCS_r(String a, String b) {
    int m = a.length() - 1;
    int n = b.length() - 1;

    if (m < 0 || n < 0)
        return "";

    if (a.charAt(m)==b.charAt(n)) {
        return LCS_r(a.substring(0, m), b.substring(0, n)) + a.substring(m);
    } 
    else {
        String s1 = LCS_r(a, b.substring(0, n));
        String s2 = LCS_r(a.substring(0, m), b);
        if (s1.length() > s2.length()) {
            return s1;
        } else {
            return s2;
        }
    }

longest common subsequence java (recursive)

2 Answers2