subject

leetcode Original link

Give you a string s , Please count and return this string Palindrome string Number of .
Palindrome string Is reading the same string as reading it backwards .
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 1：
Input ：s = “abc”
Output ：3
explain ： Three palindrome strings : “a”, “b”, “c”

Example 2：
Input ：s = “aaa”
Output ：6
explain ：6 Palindrome substrings : “a”, “a”, “a”, “aa”, “aa”, “aaa”

Tips ：
1 <= s.length <= 1000
s It's made up of lowercase letters

Ideas

Train of thought ： double for Circular violence

Train of thought two ： Dynamic programming

• set up dp[i][j] Indicates the interval [i,j]（ Left and right closed ） Whether the substring of is a palindrome string , Yes, it is true, Otherwise false
• Recursive relations , It is divided into 2 In this case
  • Situation 1 ：s[i] !== s[j], Then interval [i,j] The substring of must not be a palindrome string ,dp[i][j] = false
  • Situation two ：s[i] === s[j], At this time, it is divided into 3 Consider two situations
    • When i === j, such as 'a' This is a palindrome string ,dp[i][j] = true
    • When j - i === 1, such as aa This also belongs to palindrome string ,dp[i][j] = true
    • When j - i > 1, Then it depends on [i+1 ,j-1] Whether it is palindrome string , When dp[i+1][j-1] === true when ,dp[i][j] = true; When dp[i+1][j-1] === false when ,dp[i][j] = false
• dp The array is all initialized to false
• From the third case in case 2 , Need basis dp[i+1][j-1] To get the value of dp[i][j] Value , and dp[i+1][j-1] stay dp[i][j] The lower left corner of the , So it lasts from left to right , From bottom to top .

Code

Train of thought ： violence

/** * @param {string} s * @return {number} */
var countSubstrings = function(s) {
    
    function isPalindrome(s , start , end){
    
        let str = s.slice(start , end + 1)
        return str === str.split('').reverse().join('')
    }

    let ans = 0

    for(let i = 0 ; i < s.length ; i++){
    
        for(let j = i ; j < s.length ; j++){
    
            if(isPalindrome(s , i , j)) ans++
        }
    }
    return ans
};

Train of thought two ： Dynamic programming

/** * @param {string} s * @return {number} */
var countSubstrings = function(s) {
    
    let len = s.length
    let ans = 0
    let dp = (new Array(len)).fill(false).map(x => (new Array(len)).fill(false))

    for(let i = len - 1 ; i >= 0 ; i--){
    
        for(let j = i ; j < len ; j++){
    
            if(s[i] === s[j]){
    
                if(j - i <= 1 || dp[i+1][j-1]){
    
                    dp[i][j] = true
                    ans++
                }else{
    
                    dp[i][j] = false
                }
            }
        }
    }

    return ans
};

Complexity

• Time complexity

  • Train of thought ：$O(n^3)$
  • Train of thought two ：$O(n^2)$

• Spatial complexity

  • Train of thought ：$O(n)$
  • Train of thought two ：$O(n^2)$

Pay attention to my special column , Update three times a day leetcode Answer key , Get stronger together ！