647. Palindromic Substrings

Medium

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

Example 1:

Input: s = "abc"
Output:
 3
Explanation:
 Three palindromic strings: "a", "b", "c".

Example 2:

Input: s = "aaa"
Output:
 6
Explanation:
 Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Constraints:

• 1 <= s.length <= 1000

• s consists of lowercase English letters.

解題

也可以用馬拉車算法

func countSubstrings(s string) int {
    ans := 0

    for i := 0; i < len(s); i++ {
        ans += expand(s, i, i) 
        ans += expand(s, i, i + 1) 
    }

    return ans
}

func expand(s string, start int, end int) int {
    count := 0

    for start >= 0 && end <= len(s) - 1  {
        if s[start] != s[end] {
            break
        }
        count++
        start--
        end++
    } 

    return count
}