打印最长公共子序列

Question

longestCommonSubsequence正在返回LCS的长度。代码运行良好。但我试图打印子序列的值。例如，它应该打印“acef”。但我的代码只打印“ae”<如何修复？

这是完整的代码https://pastebin.com/Sq4QMtxF

//Code to print the LCS
        int x = a.length();
        int y = b.length();

        String s = "";

        while (x > 0 && y > 0) {
            if (a.charAt(x - 1) == b.charAt(y - 1)) {
                s = a.charAt(x - 1) + s;
                x--;
                y--;
            } else {
                if (memo[x - 1][y] > memo[x][y - 1])
                    x--;
                else
                    y--;
            }
        }
        System.out.println(s);

Answer 1

获取LCS的代码使用自顶向下的方法，您的备忘录是从0,0构建的，因此您的答案是在备忘录[0][0]中。

为了从备忘录中获取LCS字符串，您需要从上到下遍历。还要使用StringBuilder而不是将其添加到String（每次添加到String时它都会创建一个新对象）。这样，更改将是：

int x = 0, y = 0;
StringBuilder sb = new StringBuilder();
while (x < a.length() && y < b.length()) {
    if (a.charAt(x) == b.charAt(y)) {
        sb.append(a.charAt(x));
        x++;
        y++;
    } else {
        if (memo[x + 1][y] > memo[x][y + 1])
            x++;
        else
            y++;
    } 
            
}
System.out.println(sb.toString());