String: number of substring palindromes

subject

Find the number of palindromes in all substrings of a string . for example

• “aaa”, Its substring is a palindrome including ：a,a,a,aa,aa,aaa.
• “abcba", Is a substring of palindromes including ：a,b,c,bcb,abcba,b,a

Their thinking

The original question can be divided into several small questions ：

1. How to get a substring ？
2. Find the number of palindromes ？

Substring

Substring . The first way is , We started at both ends of the string , Move the double pointer inward , Judge whether there is palindrome in the interval . And here we are going to use the second method , And the center of the string spreads outward , Request palindrome .

Number of palindromes

Like strings s = “abcba”, We use c center , The pointer moves left and right 1 position , Get the substring “bcb”, So we know that this is a palindrome , The length is 3. Then continue to move the pointer to the left and right , Get a new palindrome abcba.
It's important to note that , The establishment of the central point . If the palindrome length is an odd number , Then there is only one character in the center of the substring ; Similarly, if the length of palindromes is even , There are two characters in the center of that substring .

According to the above ideas , We can get the following code ：

Code

class Solution {
    
    public int countSubstrings(String s) {
    
        if(s == null || s.length() == 0) {
    
            return 0;
        }
         int count = 0;
         for(int i = 0; i < s.length(); i++) {
        // Enumerate each character of the string , From left to right .
             // Focus on each point , Spread to the left and right for palindromes .
             count += countPalidrome(s, i, i); // Confirm the center point 
             count += countPalidrome(s, i, i + 1); // Consider the case where the palindrome length is even , Confirm that the center point is two numbers 
         }
        return count;
    }

    private int countPalidrome(String s, int start, int end) {
    
        int count = 0;
        while(start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
    
            count++;
            start--;
            end++;
        }
        return count;
    }
}

summary

Find the number of substring palindromes . You can take a substring centered , The way of outward diffusion , Move the pointer to find the number of palindromes . It should be noted that the selection of the center point is divided into two cases: even palindrome length and odd palindrome length .