Author：baiyucraft
BLog： baiyucraft’s Home
一、题目描述
题目地址：5. 最长回文子串
给你一个字符串s，找到s中最长的回文子串。
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。
输入：s = “cbbd”
输出：“bb”
输入：s = “a”
输出：“a”
输入：s = “ac”
输出：“a”
二、思路以及代码
1.暴力解法
最朴素的暴力解法，遍历每个子串，判断是否为回文串，结果显然超时了。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
max_pac = 1
max_s = s[0]
for i in range(n):
for j in range(n, i + max_pac, -1):
if self.isPalindrome(s[i:j]):
max_pac = j - i
max_s = s[i:j]
break
return max_s
def isPalindrome(self, s: str) -> bool:
n = len(s)
mid = len(s) >> 1
for i in range(mid):
if s[i] != s[n - 1 - i]:
return False
return True
|
复杂度分析：
时间复杂度：o(n3)
空间复杂度：o(1)
2.动态规划
思路： 对于一个回文串来说，首尾去掉一个字符后，还是回文串。所以我们首先用dp[i][j]来表示s的子串s[i:j + 1]是否为回文串，如果是回文串，则为True，反之则为False。
根据我们的分析，动态规划的状态转移方程为dp[i][j] = dp[i + 1][j - 1] and s[i] == s[j]
针对边界条件，即子串长度为1或2的时候，对于长度为1的子串，显然是回文串；对于长度为2的子串，两个字母相同的就是回文串，因此边界条件是dp[i][i] = True，dp[i][i + 1] = (s[i] == s[i + 1])
动画：
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
if n < 2:
return s
max_pac = 1
max_s = s[0]
dp = [[False] * n for _ in range(n)]
for i in range(n):
dp[i][i] = True
for i in range(n - 1):
if s[i] == s[i + 1]:
dp[i][i + 1] = True
if max_pac < 2:
max_pac = 2
max_s = s[i:i + 2]
for length in range(3, n + 1):
for i in range(n - length + 1):
j = length + i - 1
if s[i] != s[j]:
dp[i][j] = False
else:
dp[i][j] = dp[i + 1][j - 1]
if dp[i][j] and length > max_pac:
max_pac = length
max_s = s[i:j + 1]
return max_s
|
复杂度分析：
时间复杂度：o(n2)
空间复杂度：o(n2)
3.中心扩展