点击这里查看原题

题目描述

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。

解题方法

中心扩散，其实就是双指针( •̀ ω •́ )y

思路

题目分析

对于例子：s = “aaa”
很容易想到用暴力的方法：列举出所有的子串，然后分别判断是不是回文子串，但是这样就会产生许多的重复遍历。
既然回文子串是中心对称的，那么我们可不可以让字符串中的每个字符分别做对称中心，然后判断两边是否相等来确定是不是回文子串呢？>w<
那么恭喜你，发现了中心扩散算法！（呱唧呱唧呱唧( •̀ ω •́ )y！）那么我们就面临着一个问题：对于长度不同的字符串，对称中心可以是一个字符（比如：bab），也可以是两个字符（比如：cbaabc）。有没有一种方法可以统一判断呢？
有的兄弟，有的！

细节

我们观察下面的规律：

发现规律了吗？没发现也没关系，我们来列举一下：
以 a₁b₁b₂a₂为例
– i = 0 时 l=0,r=0 左中心为a₁，右中心也为a₁，左右中心重合
– i = 1 时 l=0,r=1 左中心为a₁，右中心为b₁
– i = 2 时 l=1,r=1 左中心为b₁，右中心也为b₁，左右中心重合
– i = 3 时 l=1,r=2 左中心为b₁，右中心为b₂
– i = 4 时 l=2,r=2 左中心为b₂，右中心也为b₂，左右中心重合
– i = 5 时 l=2,r=3 左中心为b₂，右中心为a₂
– i = 6 时 l=3,r=3（ 左中心为a₂，右中心也为a₂，左右中心重合
看出来i和l,r的关系了吗？l=i/2,r= l+i%2,并且 i<=2*n-2(n为字符串长度)!>w<
然后l向左移动，r向右移动，如果str[l]=str[r],就说明str[l,r]是一个回文子串，l,r继续向两边扩散，直到当前字串不是回文子串，即str[l]!=str[r]时,我们就去下一个对称中心继续寻找回文子串>w<

代码实现

基于以上的分析我们就可以写出代码了：

class Solution {
public:
    int countSubstrings(string s) 
    {
        int n = s.size();
        if(n == 0)
        {
            return 1;
        }
        int ans = 0;    
        for(int i = 0; i < 2*n-1; i++)
        {
            int l = i/2;//左中心
            int r = l + (i%2);//右中心
            while(l >= 0 && r < n && s[l] == s[r])
            {
                l--;
                r++;
                ans++;//每次找到一个回文子串答案+1
            }
        }
        return ans;
    }
};

至此这题就完成了，感谢观看！（呱唧呱唧呱唧>w<）