博客

一.题目描述

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。

示例 1:

输入: “abc”

输出: 3

解释: 三个回文子串: “a”, “b”, “c”.

示例 2:

输入: “aaa”

输出: 6

说明: 6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”.

注意:

输入的字符串长度不会超过1000。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/palindromic-substrings

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二.思路

思路是求解以每个元素结尾的回文子串的个数，

当前元素和前一个元素的回文子串的联系是：记录前一个元素的回文子串的起始位置，比如为1,4,7,那么如果当前的元素s[i]跟s[0],s[3],s[6]相等，当前元素对应的回文子串的个数就加1，当前的元素还有可能跟前一个元素构成回文子串，这个也要独立判断

总的思路还是找当前元素跟前一个元素的关系

代码如下：

import copy
class Solution:
    def countSubstrings(self, s: str) -> int:
        Index=[0]
        Result=1
        for i in range(1,len(s)):
            Index1=[i]
            if s[i-1]==s[i]:
                Index1.append(i-1)
            for SIndex in Index:
                if (SIndex-1>=0 and s[SIndex-1]==s[i]):
                    Index1.append(SIndex-1)
            Index=copy.deepcopy(Index1)
            Result+=len(Index)
        return Result