516. Longest Palindromic Subsequence

516. Longest Palindromic Subsequence

Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.

Example 1:
Input:

"bbbab"

Output:

4

One possible longest palindromic subsequence is “bbbb”.

注意这里是subsequence，而不是substring

Example 2:
Input:

"cbbd"

Output:

2

One possible longest palindromic subsequence is “bb”.

solution1

首先我们要了解什么是最长回文子序列

经典算法——最长回文子序列中这样解释道：

一个字符串有许多子序列，比如字符串cabbeaf，它的子序列有c、abb、e、a、f，可以通过删除某些字符而变成回文字符串，字符串“cabbeaf”，删掉‘c’、‘e’、‘f’后剩下的子串“abba”就是回文字符串，也是其中最长的回文子序列。注意和最长回文子串区别，最长回文子串必须是连续的，这里的最长回文子序列，可以是不连续的，这就是最长回文子序列LPS问题。

下面的视频来自于

Longest Palindromic Subsequence | Dynamic Programming | Set 12 | GeeksforGeeks

class Solution {
    public int longestPalindromeSubseq(String s) {
        if(s == null || s.length() == 0)
            return 0;
        int len = s.length();
        int[][] max = new int[len][len];
        
        
        for(int i = 0; i < len; i++){
            max[i][i] = 1;
        }
        
        for(int l = 1; l <= len; l++){
            for(int start = 0; start < len - l; start++){
                int end = start + l;
                if(s.charAt(start) == s.charAt(end)){
                    max[start][end] = max[start+1][end-1] + 2;
                }else{
                    max[start][end] = Math.max(max[start+1][end],max[start][end-1]);
                }
            }
        }
        return max[0][len-1];
        
    }
}

solution2_not ac

class Solution {
   int left = 0;
    int right = 0;

    int maxlen = 0;
    public int longestPalindromeSubseq(String s) {
        int longestLen = 1;

        if(s == null || s.length() == 0) return 0;
        if(s.length() == 1) return 1;

        int len = s.length();


        for(int j = 1; j <= len - 1; j++){
            for(int i = 0; i < j; i++){

                maxlen = 0;
                String s1 = s.substring(i, j+1);
                if(isPalindrome(s1,0,s1.length()-1))
                {
                    maxlen += right-left +1;
                    longestLen = Math.max(maxlen,longestLen);

                }
            }
        }


        return longestLen;
    }


    public boolean isPalindrome(String s,int start,int end){

        if(s.length() == 1 ) {
            left = start;
            right = end;
            return true;
        }

        if(s.charAt(start) == s.charAt(end) ){
            if(end - start <= 2){
                left = start;
                right = end;
                return true;

            }else {
                maxlen += 2;
                String substring = s.substring(start + 1, end);
                return  isPalindrome(substring,0,substring.length()-1);
            }


        }else {
            if(end - start == 1)
                return false;
            else if(s.charAt(start) == s.charAt(end-1) || s.charAt(start+1) == s.charAt(end)){
                if(s.charAt(start) == s.charAt(end-1) ){
                    String s3 = s.substring(start, end );
                    return isPalindrome(s3,0,s3.length()-1);
                }

                if(s.charAt(start+1) == s.charAt(end)){
                    String s2 = s.substring(start + 1, end + 1);
                    return isPalindrome(s2,0,s2.length()-1);

                }
            }
        }

        return false;

    }


}