Palindrome related topics

647. Palindrome string

subject

Give you a string s , Please count and return this string Palindrome string Number of . Palindrome characters Is reading the same string as reading it backwards . A substring is a sequence of consecutive characters in a string .
A substring with different start or end positions , Even if it's made up of the same characters , It's also seen as a different substring .
Example ：

Ideas

1. determine dp Array （dp table） And the meaning of subscripts
Boolean type dp[i][j]： Express Range [i,j] （ Note that the left is closed and the right is closed ） Whether the substring of is a palindrome substring , If it is dp[i][j] by true, Otherwise false.
2. Determine the recurrence formula
s[i] And s[j] It's not equal return false;
s[i] And s[j] equal
Situation 1 ： Subscript i And j identical , The same character, for example a, Palindromes, of course i==j
Situation two ： Subscript i And j The difference is 1, for example aa, It's also palindrome substring j - i == 1
Situation three ： Subscript ：i And j The difference is greater than 1 When , for example cabac, here s[i] And s[j] It's the same , Let's see i To j Whether the interval is a palindrome substring depends on aba Is palindrome enough , that aba The interval is i+1 And j-1 Section , Whether this interval is palindrome depends on **dp[i + 1][j - 1]** Is it true.
3. initialization
4. Determine the traversal order
Case 3 is based on dp[i + 1][j - 1] Is it true, In the face of dp[i][j] Assign a value true Of .dp[i + 1][j - 1] stay dp[i][j] The lower left corner of the , Pictured ：
Be sure to go from bottom to top , Traverse from left to right , This guarantee dp[i + 1][j - 1] It's all calculated .

Code

class Solution {
    
    public int countSubstrings(String s) {
    
        // Dynamic programming  dp[i][j]  representative [i,j] Whether the palindrome character is in the interval 
        //dp[i][j] from dp[i-1][j+1] decision 
        int len  = s.length();
        boolean[][] dp = new boolean[len][len];
        int res = 0;
        // From bottom to top , Traverse from left to right 
        for(int i = len-1; i >= 0; i--){
    
            for(int j = i; j < len; j++){
    
                if(s.charAt(i) == s.charAt(j)){
    
                    //(s.charAt(i)==s.charAt(j)  when , When the number of elements is 1,2,3 Time , Must be a palindrome substring 
                    if(j - i <= 1){
    
                        res++;
                        dp[i][j] = true;
                    }else if(dp[i+1][j-1] == true){
    
                        res++;
                        dp[i][j] = true;
                    }
                }
            
            }
        }
        return res;
    }
}

516. The longest palindrome subsequence

Give you a string s , Find out The longest palindrome subsequence , And return the length of the sequence .
Subsequence is defined as ： Without changing the order of the remaining characters , A sequence formed by deleting some characters or not deleting any characters .
Example ：

Ideas

1. determine dp Array （dp table） And the meaning of subscripts
dp[i][j]： character string s stay **[i, j] Range ** The length of the longest palindrome subsequence in is dp[i][j].

2. Determine the recurrence formula
In the question of judging palindrome substrings , The key logic is to look at s[i] And s[j] Are they the same? .
（1） If s[i] And s[j] identical , that dp[i][j] = dp[i + 1][j - 1] + 2;

（2） If s[i] And s[j] inequality , explain s[i] and s[j] Join in at the same time Does not increase [i,j] The length of the interval palindrome substring , Then join s[i]、s[j] See which can form the longest palindrome subsequence .

Join in s[j] The length of palindrome subsequence of is dp[i + 1][j].
Join in s[i] The length of palindrome subsequence of is dp[i][j - 1].
dp[i][j] It must be the largest , namely ：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
3. initialization
First of all, consider When i and j identical The situation of , From the recursive formula ：dp[i][j] = dp[i + 1][j - 1] + 2; It can be seen that The recursive formula dp[i][j] Yes, it cannot be calculated i and j At the same time .
So you need to initialize it manually , When i And j identical , that dp[i][j] It must be equal to 1 Of , namely ： The length of the palindrome subsequence of a character is 1.
Other situations dp[i][j] For the initial 0 Just go , So the recurrence formula ：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); in dp[i][j] Will not be overwritten by the initial value .
4. Determine the traversal order
So traverse i Be sure to traverse from bottom to top , In this way, we can guarantee , The data in the next row is calculated .

Code

class Solution {
    
    public int longestPalindromeSubseq(String s) {
    
        // Dynamic programming  dp[i][j] On behalf of the [i,j] The length of the longest palindrome subsequence on 
        int len = s.length();
        int[][] dp = new int[len+1][len+1];
        // From bottom to top , Traverse from left to right 
        for(int i = len-1; i >= 0; i--){
    
            for(int j = i+1; j < len; j++){
    
                // When i and j Initialize at the same time 
                dp[i][i] = 1;
                if(s.charAt(i) == s.charAt(j)){
    
                    dp[i][j] = dp[i+1][j-1] + 2;
                }else{
    
                    dp[i][j] = Math.max(dp[i][j-1],dp[i+1][j]);
                }   
            }
        }
        return dp[0][len-1];
    }
}