647 .回文子字符串
主题
给定字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始或结束位置的子列被视为不同的子列，即使它们由相同的字符组成。
示例1 :
输入： abc
输出： 3
解释： 3个回文子串： 'a '、' b '、' c '
示例2 :
输入： aaa
输出： 6
解释： 6个回文子串： 'a '、' a '、' a '、' aa '、' aa '、' aa '、' aaa '
提示：
的字符串长度不超过1000。
解开想法
想法：动态规划
请先看看主题。 主题要求在给定的字符串中，字符串中有多少个回文子串。 这里，不同的开始位置或结束位置的部分列即使相同也被视为不同的部分列。
其实读了主题，我们想到最直接的想法，就是先列举文字的组合，判断这些文字组合而成的子串是否是回文串就可以了。
现在，让我们用这个直接的方法代码实现一下。
类解决方案：
defcountsubstrings(self，s: str )- int:
defis _ palindrome (字符串) :
“”判断传递的字符串是否为回文串
''''
left=0
right=len (字符串)- 1
while left right:
if字符串[ left ]！=string[right]:
返回假
left =1
right -=1
返回真
#计数
计数=0
#枚举字符集
forIinrange(Len ) s ) ) :
forjinrange(I，Len ) s ) ) :
判断#字符组合是否为回文串
#计数1的情况下，否则跳过
sub_string=s[i:j 1]
ifis_palindrome(sub_string ) :
计数=1
返回计数
在上述方法中，如果字符串的长度为n，则枚举所有子字符串需要$o(n^2) $的时间，而判断子字符串是否返回字符串需要$o ) $ s ) $的时间。 因为s是子字符串的长度，所以整个算法的时间为$o(n^3) $。
在此，我们也从侧面说明在Python上执行结果超时，可以考虑。 在此执行超时的原因是如上所述，频繁地对字符串进行切片，或判断子串是否是回文串。
让我们看看如何运用动态规划的思路来解决。
动态规划
假设s[i.j](i.j表示该区间内的字符中包含I、j )为回文串。 那么，s[i-1.j 1]只有在s[i-1]==s[j 1]的情况下才是回文串。
定义状态
假设现在dp[i][j]指示s[i.j]是否为回文串。
状态转移方程
接下来，分析一下子字符串作为回文字符串成立的情况。
i==j时，表示是单字符，单字符也是回文串
在s[i]==s[j]且i 1=j (或i=j-1 )的情况下，这里表示两个字符，如果相同，则同样地回文串；
如果dp[i 1][j-1]==True，即s[i 1.j-1]是回文串，如果s[i]==s[j]，则dp[i][j]也同样是回文串。
可以看出，第二、第三种情况可以合并为一个。
在s[i]==s[j]的情况下，如果i==j-1或dp[i 1][j-1]==True中的一个成立，则dp[i][j]全部为True，s[i.j]为回文公式如下。
$dp[i][j]=True，qquad if，(s[i]==s[j]，and，(i==j-1，or，dp[i 1][j-1] ) ) $
从另一种情况可以看出，实际上在i==j的情况下，s[i]==s[j]也成立。 但在这种情况下，i=j-0。
那么，现在将第一种情况向上合并，即i=j - 1或i - j=-1，则表达式如下：
$dp[i][j]=True，qquad if，(s[i]==s[j]，and，(i-j=-1，or，dp[i 1][j-1] ) ) $
复杂度分析：
时间复杂性： $o(n^2) $
空间复杂性： $o(n^2) $，dp数组开销。
也有中心扩散法，该方法可以将空间复杂度降低到常数时间复杂度$o(1) $。 这里详细介绍了官方解决问题的方法，感兴趣的朋友请通过以下链接的入口进行理解。
具体代码实现如下：
代码实现
类解决方案：
defcountsubstrings(self，s: str )- int:
#计数
计数=0
n=len(s )
定义#DP数组并初始化为False
DP=[[false]*nfor_inrange(n ) ]
#从右向左遍历以填充dp数组
forIinrange(n-1，-1，-1) :
forjinrange(I，n ) :
#从文章中得到的状态转移方程
ifs [ I ]==s [ j ] and (I-j=-1 ordp [ i1 ] [ j-1 ] ) :
dp[i][j]=True
计数=1
返回计数
实现结果
请关注
公众号【本所集录】