利用回溯理解LCS

Question

我在试着理解回溯。为此，我从以下链接- http://en.wikibooks.org/wiki/Algorithms/Backtracking开始

它解释了LCS。我知道动态编程解决方案会更快，但我一步一步地走。他们提供的伪代码是吗？为此: String[] a= {"The“、”The“、"great”、"square“、"has”、"a“、”同“、"no”、“String[]”}；String[]b= {"The“、”The“、"great”、“String[]”、"has“、"no”、"a“、”同“、"form"}；

上面还印着“不”。

这是我的尝试，有人能改进/纠正它吗？

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

使用@David的建议更新的方法-问题1-它仍然打印出"no“问题2-它仍然给出多余的值。我觉得这是回溯的副作用。

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

Answer 1

你违反了变量和它们的值之间的区别。if语句的真正分支假设getLongestCommonSubsequence将其输出留在作为参数传递的特定ArrayList中。另一方面，false分支分配两个新的ArrayList，并将输出留在一个或另一个中，而不是请求的存储位置。而不是output = discardA;，您需要执行output.addAll(discardA);，以便将项复制到正确的列表中(同样也适用于discardB)。另外，第二个if应该有一个else，这样就执行了一个addAll。

此外，您应该使用a[0].equals(b[0])而不是a[0] == b[0]，但是只要测试字符串是interned，这不会导致错误。

编辑:以下是我的想法：

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