给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。
示例 2：
输入：s = “cbbd”
输出：“bb”
提示：
- 1 <= s.length <= 1000
- s 仅由数字和英文字母组成
解法
思路一：暴力枚举 + 递归判断回文
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution:
def longestPalindrome(self, s: str) -> str:
longest = s[0]
for i in range(len(s)):
for j in range(i+1, len(s)+1):
current = s[i:j]
if self.isPalindrome(current) and len(current) > len(longest):
longest = current
return longest
def isPalindrome(self, s: str) -> bool:
if len(s) <= 1:
return True
else:
return s[0] == s[-1] and self.isPalindrome(s[1:-1])
|
- 时间复杂度：$O(n^3)$
- 两层循环枚举所有子串
- 每个子串递归判断是否为回文
思路二：中心扩展法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution:
def longestPalindrome(self, s: str) -> str:
def expand(left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return s[left+1:right]
longest = ""
for i in range(len(s)):
current = expand(i, i)
if len(current) > len(longest):
longest = current
current = expand(i, i+1)
if len(current) > len(longest):
longest = current
return longest
|
- 时间复杂度：$O(n^2)$
- 定义帮助函数 expand，返回的必然是一个回文子串
- 从中心向左右扩展，直到不相等
expand(i, i) 以单个字符为中心扩展，处理奇数长度的回文子串expand(i, i+1) 以两个字符为中心扩展，处理偶数长度的回文子串