LeetCode 647. Palindromic Substrings

题目描述

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

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

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

tag

回文题 子串题 DP

样例

1
2
3
输入: "aaa"
输出: 6
说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".

算法1

(枚举 中心扩散) O(n^2)
思路
复杂度分析:
python 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class :
def countSubstrings(self, s: str) -> int:
n = len(s)
res = 0
for i in range(n):

j = 0
while 0 <= i - j and i + j < n and s[i - j] == s[i + j]:
res += 1
j += 1

k = 1
while 0 <= i - k + 1 and i + k < n and s[i - k + 1] == s[i + k]:
res += 1
k += 1

return res

算法2

(DP) O(n^2)
思路

dp[i][j] 表示 s[i : j + 1]是否为回文串

dp[i][j] is true if s[i] == s[j] and dp[i+1][j-1] is true, j - i >= 2

dp[i][j] is true if s[i] == s[j], j - i == 1

dp[i][j] is true if j - i == 0

复杂度分析:
python 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def countSubstrings(self, s: str) -> int:
if not s:
return 0
n = len(s)
count = 0
dp = [[False for _ in range(n)] for _ in range(n)]

for j in range(n):
for i in range(j + 1):
if i == j:
dp[i][j] = True
elif j - i == 1:
dp[i][j] = (s[i] == s[j])
else:
dp[i][j] = (s[i] == s[j] and dp[i + 1][j - 1])

if dp[i][j]:
count += 1

return count

算法3

(马拉车) O(n)
思路
复杂度分析:
python 代码