最长公共子序列打印

Question

longestCommonSubsequence返回LCS的长度。密码很好用。但是我试图在下面打印子序列.For的值--它应该打印"acef“.But --我的代码只打印"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构建的，所以您的答案是在memo[0][0]。

为了从备忘录中获得LCS字符串，您需要从上到下遍历。还可以使用StringBuilder，而不是将其添加到字符串中(每次添加到字符串中时，它都会创建一个新对象)。这样做的改变将是：

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