647. 回文子串

题目：

 复制代码
给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入："abc"
输出：3
解释：三个回文子串: "a", "b", "c"
示例 2：
输入："aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindromic-substrings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

答案：

时间：

10min

 复制代码
class Solution:
    def countSubstrings(self, s: str) -> int:
        k="@"
        for word in s:
            k+=word
            k+="#"
        k+="&"
        n=len(k)
        ans=0
        for i in range(1,n-1):
            count=0
            j=0
            while i+j<n and i-j>=0 :
                if k[i-j]=="#":
                    j+=1
                    continue
                if k[i-j]==k[i+j]:
                    count+=1
                    j+=1
                else:
                    break
            ans+= count
        return ans

要点：

1. 预处理。@a#b#c#&

遇到”#”，不管，扩张即可，这个算法的预处理包括奇回文串和偶回文串
复杂度 O(N^2)

其他：

代码报错：无