Understanding LCS using backtracking

Question

I am trying to understand backtracking. For that I started with the following link - http://en.wikibooks.org/wiki/Algorithms/Backtracking

It has explained LCS. I understand dynamic programming solution will be faster, but I am taking one step at a time. Is the pseudo code they have provided, correct? For this : String[] a = {"The", "great", "square", "has", "a", "same", "no", "corners"}; String[] b = {"The", "great", "image", "has", "no", "a", "same", "form"};

it also prints "no".

This is my attempt, can someone please improve / correct it.

public ArrayList<String> getLongestCommonSubsequence(String[] a , String[] b, ArrayList<String> output)
{
    if(a.length == 0 || b.length == 0)
        return output;

    if(a[0]==b[0])
    {   
        output.add(a[0]);
        getLongestCommonSubsequence(Arrays.copyOfRange(a, 1, a.length), Arrays.copyOfRange(b, 1, b.length), output);
    }
    else
    {
        ArrayList<String> discardA = getLongestCommonSubsequence(Arrays.copyOfRange(a, 1, a.length), b, new ArrayList<String>());
        ArrayList<String> discardB = getLongestCommonSubsequence(a, Arrays.copyOfRange(b, 1, b.length), new ArrayList<String>());

        if(discardA.size() > discardB.size())
            output = discardA;
        if(discardB.size() > discardA.size())
            output = discardB;
    }
    return output;
}

Updated method with the suggestion from @David Eisenstat - Problem 1 - It still prints out "no" Problem 2 - It gives out redundant values still. I think that's a side effect of using backtracking.

public ArrayList<String> getLongestCommonSubsequence(String[] a , String[] b, ArrayList<String> output)
{
    if(a.length == 0 || b.length == 0)
        return output;

    if(a[0].equals(b[0]))
    {   
        output.add(a[0]);
        getLongestCommonSubsequence(Arrays.copyOfRange(a, 1, a.length), Arrays.copyOfRange(b, 1, b.length), output);
    }
    else
    {
        ArrayList<String> discardA = getLongestCommonSubsequence(Arrays.copyOfRange(a, 1, a.length), b, output);
        ArrayList<String> discardB = getLongestCommonSubsequence(a, Arrays.copyOfRange(b, 1, b.length), output);

        if(discardA.size() > discardB.size())
            output.addAll(discardA);
        else if(discardB.size() > discardA.size())
            output.addAll(discardB);
    }
    return output;
}

score 0 · Accepted Answer · edited May 23 '17 at 11:49

You've run afoul of the distinction between variables and their values. The true branch of the if statement assumes that getLongestCommonSubsequence will leave its output in the specific ArrayList passed as an argument. The false branch, on the other hand, allocates two new ArrayLists and leaves the output in one or the other instead of the requested storage location. Instead of output = discardA; you need to do output.addAll(discardA);, so that the items are copied to the correct list (and likewise for discardB). Also, the second if there should be an else, so that exactly one addAll is performed.

Additionally, you should be using a[0].equals(b[0]) instead of a[0] == b[0], though that won't cause a bug as long as your test strings are interned.

EDIT: Here's what I had in mind:

import java.util.*;

public class LCS {
    static void getLongestCommonSubsequence(String[] a, String[] b, List<String> output) {
        if (a.length == 0 || b.length == 0) {
        } else if (a[0].equals(b[0])) {
            output.add(a[0]);
            getLongestCommonSubsequence(Arrays.copyOfRange(a, 1, a.length), Arrays.copyOfRange(b, 1, b.length), output);
        } else {
            List<String> discardA = new ArrayList<String>();
            getLongestCommonSubsequence(Arrays.copyOfRange(a, 1, a.length), b, discardA);
            List<String> discardB = new ArrayList<String>();
            getLongestCommonSubsequence(a, Arrays.copyOfRange(b, 1, b.length), discardB);
            if (discardA.size() >= discardB.size()) {
                output.addAll(discardA);
            } else {
                output.addAll(discardB);
            }
        }
    }

    public static void main(String[] args) {
        String[] a = {"The", "great", "square", "has", "a", "same", "no", "corners"};
        String[] b = {"The", "great", "image", "has", "no", "a", "same", "form"};
        List<String> output = new ArrayList<String>();
        getLongestCommonSubsequence(a, b, output);
        System.out.println(output);
    }
}

Hi @DavidEisenstat, Thanks for replying. I updated the original post with your suggestions. Actually the addAll, is what I had done earlier, but it didn't work with that. So, I removed it to follow what was suggested in the pseudo code. It still doesn't work. Any ideas? — ND27, Aug 17 '14 at 21:21
@ND27 You made a couple more tweaks that I hadn't intended -- it's still necessary to run the recursive calls into scratch lists. I pasted my version of the LCS code into my answer. — David Eisenstat, Aug 17 '14 at 21:36

Understanding LCS using backtracking

1 Answers1