打印最长公共子序列

Question

longestcommon子序列返回LCS的长度。代码运行良好。但是我试图打印子序列的值。对于下面的例子，它应该打印"acef"但是我的代码只打印&;&;
如何修复?

这里是完整的代码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]。

为了从memo中获取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());