题目描述
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.
Note:
The input string length won’t exceed 1000.
Example1:
Input: “abc”
Output: 3
Explanation: Three palindromic strings: “a”, “b”, “c”.
Example2:
Input: “aaa”
Output: 6
Explanation: Six palindromic strings: “a”, “a”, “a”, “aa”, “aa”, “aaa”.
Note:
All inputs will be in lowercase. The order of your output does not matter.
解题思路
- 以字符串中的每一个字符都当作回文串中间的位置，然后向两边扩散，每当成功匹配两个左右两个字符，结果 res 自增1，然后再比较下一对。
- 注意回文字符串有奇数和偶数两种形式
- 如果是奇数长度，那么i位置就是中间那个字符的位置，所以左右两遍都从i开始遍历；
- 如果是偶数长度的，那么i是最中间两个字符的左边那个，右边那个就是 i+1，这样就能 cover 所有的情况，而且都是不同的回文子字符串
class Solution {
public:
int countSubstrings(string s) {
int res = 0;
for(int i = 0; i < s.size(); i++){
fun_helper(s, i, i, res); // 以i为单位往两边扩散
fun_helper(s, i, i + 1, res); // 以i， i + 1为单位往两边扩散
}
return res;
}
void fun_helper(string s, int i, int j, int& res){
while(i >= 0 && j < s.size() && s[i] == s[j]){
res ++;
i--;
j++;
}
}
};
