共计 2075 个字符，预计需要花费 6 分钟才能阅读完成。
647. 回文子串
题目起源：力扣（LeetCode）[https://leetcode-cn.com/probl…
](https://leetcode-cn.com/probl…
)
题目
给定一个字符串，你的工作是计算这个字符串中有多少个回文子串。
具备不同开始地位或完结地位的子串，即便是由雷同的字符组成，也会被视作不同的子串。
示例 1：
输出："abc"
输入：3
解释：三个回文子串: "a", "b", "c"示例 2：
输出："aaa"
输入：6
解释：6 个回文子串: "a", "a", "a", "aa", "aa", "aaa"提醒：
- 输出的字符串长度不会超过 1000。
解题思路
思路：动静布局
先看题目，题目要求在给定的字符串中，求得字符串中有多少个回文子串。其中提及，不同开始或完结地位的子串，即使雷同也视为不同子串。
其实看完题目，咱们想到最间接的想法就是，先枚举字符的组合，判断这些字符组合成的子串是否是回文串即可。
当初咱们来看看，用这种间接的办法代码实现：
class Solution:
def countSubstrings(self, s: str) -> int:
def is_palindrome(string):
"""判断传入字符串是否是回文串"""
left = 0
right = len(string) - 1
while left < right:
if string[left] != string[right]:
return False
left += 1
right -= 1
return True
# 计数
count = 0
# 枚举字符组合
for i in range(len(s)):
for j in range(i, len(s)):
# 判断字符组合是否是回文串
# 若是计数 +1，否则跳过
sub_string = s[i:j+1]
if is_palindrome(sub_string):
count += 1
return count下面的办法中，假如字符串长度为 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)$。这里在官网题解有给出具体内容，有趣味的能够从上面链接入口进入理解。
https://leetcode-cn.com/problems/palindromic-substrings/solution/hui-wen-zi-chuan-by-leetcode-solution/
具体的代码实现如下。
代码实现
class Solution:
def countSubstrings(self, s: str) -> int:
# 计数
count = 0
n = len(s)
# 定义 dp 数组，初始化为 False
dp = [[False] * n for _ in range(n)]
# 咱们从右往左遍历，填充 dp 数组
for i in range(n-1, -1, -1):
for j in range(i, n):
# 依据文章得出的状态转移方程
if s[i]==s[j] and (i-j>=-1 or dp[i+1][j-1]):
dp[i][j] = True
count += 1
return count
实现后果
欢送关注
公众号【书所集录】
