Leetcode day 17

5. Longest text substring

516. The longest palindrome subsequence

---

5. Longest text substring

 Give you a string  s, find  s  The longest palindrome substring in .

 

 Example  1：

 Input ：s = "babad"
 Output ："bab"
 explain ："aba"  It's the same answer .
 Example  2：

 Input ：s = "cbbd"
 Output ："bb"
 

 Tips ：

1 <= s.length <= 1000
s  It consists only of numbers and English letters 

 source ： Power button （LeetCode）
 link ：https://leetcode-cn.com/problems/longest-palindromic-substring
 Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Realize the idea ：

This problem has been done before , But this time, there are still many problems , Special attention should be paid here to the fact that the order of the two loops of the function body cannot be exchanged , First deal with a certain kind of palindrome string with fixed length , Handle in the extended drive .

Implementation code ：
 

class Solution {
    public String longestPalindrome(String s) {
        int len=s.length();
        if(len<2) return s;
        int begin=0,end=0;
        int maxlen=0;
        boolean[][] dp=new boolean[len][len];
        char[] charArray=s.toCharArray();
        for(int i=0;i<len;i++){
            dp[i][i]=true;
        }
        for(int l=2;l<=len;l++){
            for(int i=0;i<len;i++){
                int j=i+l-1;
                if(j>=len){
                    break;
                }
                if(charArray[i]!=charArray[j]){
                    dp[i][j]=false;
                }else{
                    if(l<=3){
                        dp[i][j]=true;
                    }else{
                        dp[i][j]=dp[i+1][j-1];
                    }
                }
                if(dp[i][j]==true&&l>maxlen){
                        maxlen=l;
                        begin=i;
                        end=j;
                    }
            }
        }
        
        return s.substring(begin,end+1);
    }
}

---

516. The longest palindrome subsequence

Realize the idea ：

I have trouble writing the code of this problem , In fact, it is a variant of the previous question , Clarify the state transition equation .

  I'm tired of writing code , But I still have the courage to post it .

Implementation code ：

class Solution {
    public int longestPalindromeSubseq(String s) {
        int len=s.length();
        if(len<2) return len;
        int begin=0,end=0;
        int maxlen=0;
        int[][] dp=new int[len][len];
        char[] charArray=s.toCharArray();
        for(int i=0;i<len;i++){
            dp[i][i]=1;
        }
        for(int l=2;l<=len;l++){
            for(int i=0;i<len;i++){
                int j=i+l-1;
                if(j>=len){
                    break;
                }
                if(charArray[i]!=charArray[j]){
                    dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
                }else{
                    if(l<=3){
                        dp[i][j]=l;
                    }else{
                        dp[i][j]=dp[i+1][j-1]+2;
                    }
                }
            }
        }
        
        return dp[0][len-1];
    }
}