Sword finger offer II 020 Number of palindrome substrings

Summary

It's still a double pointer , But this time the double pointer moves to both sides at the center of the substring .

subject

Given a string s , Please calculate how many palindrome substrings there are in this 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 .

Ideas

This time you need to enumerate all the substrings , To determine whether it is a palindrome substring .

In the past, double pointers started from the leftmost side , The right pointer moves to determine the range of the substring . This time we focus on one character , The double pointer starts with the center character , Move to both sides . Of course , Palindrome string length has odd number and even number , So there is one or two cases at our starting point .

solution

Code

public int countSubstrings(String s) {
    
    int count = 0;
    for (int i = 0; i < s.length(); i++) {
    
        count += palindromeCount(s, i, i);
        count += palindromeCount(s, i, i + 1);
    }
    return count;
}

public int palindromeCount(String s, int left, int right) {
    
    int count = 0;
    while (left >= 0 && right < s.length()) {
    
        if (s.charAt(left) == s.charAt(right)) {
    
            count++;
            left--;
            right++;
        } else {
    
            break;
        }
    }
    return count;
}