public int longestPalindromeSubseq(String s) {
if (s == null  s.length() == 0) return 0;
int len = s.length();
String revert = new StringBuilder(s).reverse().toString();
int [] last = new int [len + 1];
int [] cur = new int [len + 1];
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
if (s.charAt(i) == revert.charAt(j)) cur[j + 1] = last[j] + 1;
else cur[j + 1] = Math.max(cur[j], last[j + 1]);
}
int [] temp = cur;
cur = last;
last = temp;
}
int max = last[len];
return max;
}
Easy Java solution, reverts string, you will find it is LCS : )


could you explain why you have to switch "last" and " cur" ? I saw a similar solution https://discuss.leetcode.com/topic/84796/longestcommonsubsequencebeats94/2, but it just simply let "row1 = row2"
class Solution { public: int longestPalindromeSubseq(string s) { string rs = s; reverse(rs.begin(), rs.end()); vector<int> row1(s.size()+1), row2(s.size()+1); for (int i=1; i<=s.size(); i++) { for (int j=1; j<=rs.size(); j++) { if (rs[j1] == s[i1]) { row2[j] = row1[j1] + 1; } else { row2[j] = max(row1[j], row2[j1]); } } row1 = row2; } return row1.back(); } };