一.题目描述
给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被计为是不同的子串。
示例 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
版权声明:本文为skj1995原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。