This topic

• 647 Palindrome string
• 516 The longest palindrome subsequence

647 Palindrome string

• DP：
  1. Definition dp Array dp[i][j] Scope of representation i To j（ Left and right closed ） Whether the substring in the palindrome substring , If so, it is true, Otherwise false;
  2. Recurrence formula if s[i] != s[j], Then for false, If s[i] == s[j], Discussion by situation , When i and j The difference is less than or equal to 1 when , by true, Otherwise, it is equal to the range i+1 To j-1（ Left and right closed ） Result ;
  3. initialization dp[i][j] For all false;
  4. The traversal order is from bottom to top , From left to right , Prevent taking range i+1 To j-1 The result of is the initialization value ;
  5. give an example .

class Solution {
    
    public int countSubstrings(String s) {
    
        //DP
        int leng = s.length();
        // Definition dp Array dp[i][j] Scope of representation i To j（ Left and right closed ） Whether the substring in the palindrome substring , If so, it is true, Otherwise false
        // initialization dp[i][j] For all false
        boolean[][] dp = new boolean[leng][leng];
        // Define results 
        int result = 0;
        // The traversal order is from bottom to top , From left to right , Prevent taking range i+1 To j-1 The result of is the initialization value 
        for(int i = leng - 1; i >= 0; i--){
    
            for(int j = i; j < leng; j++){
    
                if(s.charAt(i) == s.charAt(j)){
    
                    if(j - i <= 1){
    
                        dp[i][j] = true;
                    }else{
    
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if(dp[i][j] == true) result++;
            }
        }
        // Return results 
        return result;
    }
}

• Double finger needling （ Less space complexity ）：

class Solution {
    
    public int countSubstrings(String s) {
    
        // Double finger needling 
        int leng = s.length();
        // Define results 
        int result = 0;
        // Spread to both sides with one or two elements as the center 
        for(int i = 0; i < leng; i++){
    
            // An element 
            result += judge(s, i, i, leng);
            // Two elements 
            result += judge(s, i, i + 1, leng);
        }
        // Return results 
        return result;
    }
    // The double pointer spreads to both sides 
    private int judge(String s, int i, int j, int leng){
    
        // Define results 
        int res = 0;
        while(i >= 0 && j < leng && s.charAt(i) == s.charAt(j)){
    
            res++;
            i--;
            j++;
        }
        return res;
    }
}

516 The longest palindrome subsequence

• Compare with the previous question 647 Palindrome string , The palindrome subsequence of this question does not require continuity , But the idea is the same .
• DP：
  1. Definition dp Array dp[i][j] Representation string s In scope i To j（ Left and right closed ） The length of the longest palindrome subsequence in is dp[i][j];
  2. Recurrence formula if s[i] == s[j], be dp[i][j] = dp[i + 1][j - 1] + 2, otherwise dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
  3. initialization dp[i][i] = 1;
  4. The traversal order is from bottom to top, left to right , Prevent taking range i+1 and j-1 Not assigned when ;
  5. give an example .

class Solution {
    
    public int longestPalindromeSubseq(String s) {
    
        //DP
        int leng = s.length();
        // Definition dp Array dp[i][j] Representation string s In scope i To j（ Left and right closed ） The length of the longest palindrome subsequence in is dp[i][j]
        int[][] dp = new int[leng][leng];
        // initialization dp[i][i] = 1
        for(int i = 0; i < leng; i++) dp[i][i] = 1;
        // The traversal order is from bottom to top, left to right , Prevent taking range i+1 and j-1 Not assigned when 
        for(int i = leng - 1; i >= 0; i--){
    
            for(int j = i + 1; j < leng; j++){
      //j from i+1 Start , because j=i Has been initialized to 1 了 
                if(s.charAt(i) == s.charAt(j)){
    
                    dp[i][j] = dp[i + 1][j - 1] + 2;    // When i and j The difference is 1 when i+1 and j-1 The exchange of upper and lower limits does not affect 
                }else{
    
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        // Return results 
        return dp[0][leng - 1];
    }
}