Easy Java solution, reverts string, you will find it is LCS : )


  • 0
    Z
    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;
        }
    

  • 0
    G

    could you explain why you have to switch "last" and " cur" ? I saw a similar solution https://discuss.leetcode.com/topic/84796/longest-common-subsequence-beats-94/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[j-1] == s[i-1]) {
                        row2[j] = row1[j-1] + 1;
                    }
                    else {
                        row2[j] = max(row1[j], row2[j-1]);
                    }
                }
                row1 = row2;
            }
            return row1.back();
        }
    };
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.