问题描述
Given a string, your task is to count how many palindromic substrings in this string.
The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.
Example 1:
Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".
Example 2:
Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
Note:
- The input string length won’t exceed 1000.
问题分析
如果是单字符串判断回文，通常做法是左右双指针向中间移动进行判断。
这里如果按照这种方式，会导致很多无效的判断。我们换一种判断方式：
- 遍历字符串，每次以当前字符为中心，不断增长两边的距离，一旦发现两端不匹配，终止当前判断；进行下一个字符
- 步骤1是针对基数个字符回文的情况，我们再针对偶数个字符回文的情况，再判断一次即可。
示例代码
func countSubstrings(s string) int {
ans := 0
for i := 0; i < len(s); i++ {
dst := 0
for {
if i-dst < 0 || i+dst > len(s)-1 {
break
}
if s[i-dst] != s[i+dst] {
break
}
ans++
dst++
}
}
for i := 0; i < len(s)-1; i++ {
dst := 0
for {
if i-dst < 0 || i+dst+1 > len(s)-1 {
break
}
if s[i-dst] != s[i+dst+1] {
break
}
ans++
dst++
}
}
return ans
}