打印最长的回文子序列

Question

我能够正确打印最长回文子序列的长度。但是我无法正确打印字符串。这是完整的问题https://leetcode.com/problems/longest-palindromic-subsequence/

输入：s="bbbab"；输出：4解释：一个可能最长回文子序列是"；bbbb"；。

我的完整解决方案是https://leetcode.com/submissions/detail/752148076/

print(s); //print the solution .But doesnt give correct answer.Below is the code snippet.

Print((函数将输出作为"；bb"；对于s＝"0"；bbbab"；。更正将打印bbbb

//use this function for printing dp array!
public void print(String str) {

int x = 0,
y = str.length() - 1; 
//   int ans=4;
String palindromicSubsequence="";

while (x <= y) {
if (str.charAt(x) == str.charAt(y)) {
palindromicSubsequence= palindromicSubsequence + str.charAt(x);
++x;
--y;
} else if ( memo[x + 1][ y] > memo[x][y - 1] ) {
++x;
} else {
--y;
}

}
System.out.println("String is " + palindromicSubsequence );

}

Answer 1

当x不等于y时，必须在回文中添加两次字符。

由于回文是从外向内构建的，因此使用两个字符串而不是一个字符串会更容易：

String left = "", right = "";

while (x < y) { // Treat the case x == y separately
if (str.charAt(x) == str.charAt(y)) {
left = left + str.charAt(x);
right = str.charAt(x) + right;
++x;
--y;
} else if (memo[x + 1][y] > memo[x][y - 1]) {
++x;
} else {
--y;
}
}
if (x == y) { // The middle character
left = left + str.charAt(x);
}
System.out.println("String is " + left + right);

最好使用StringBuffer