问题描述
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
解题思路
滑动窗口由小到大。
1
2
3
4
5
6
7
8
9
10
11
12 | class Solution:
def longestPalindrome(self, s: str) -> str:
left = max_len = 0
n = len(s)
for i in range(n):
for j in range(i, n):
t = s[i : j + 1]
k = len(t)
if t == t[::-1] and k > max_len:
max_len = k
left = i
return s[left : left + max_len]
|
结果超时。
滑动窗口由大到小。因为是计算最长回文，在上面第二层循环中，可以让 j 递减，这样只要当前的字符串是回文，它就是以 i 为起点的最长回文。
1
2
3
4
5
6
7
8
9
10
11
12
13 | class Solution:
def longestPalindrome(self, s: str) -> str:
left = max_len = 0
n = len(s)
for i in range(n):
for j in range(n - 1, i - 1, -1):
t = s[i : j + 1]
if t == t[::-1]:
if len(t) > max_len:
max_len = len(t)
left = i
break
return s[left : left + max_len]
|
结果超时。但是通过的测例更多了一点。
再改进一下。
第 i 次循环得到的最大回文长度为 max_len，第 i+1 中，j 只用从 n-1 到 i+1+max_len 就行，否则 j 再小得到的最大回文长度也不会超过 max_len 了。
1
2
3
4
5
6
7
8
9
10
11
12 | class Solution:
def longestPalindrome(self, s: str) -> str:
left = max_len = 0
n = len(s)
for i in range(n):
for j in range(n - 1, i + max_len - 1, -1):
t = s[i : j + 1]
if t == t[::-1]:
max_len = len(t)
left = i
break
return s[left : left + max_len]
|
在超时边缘徘徊，第一次看到运行时长这么长的并且还通过了。
若 s[i:j] 为回文，则 s[i+1:j-1] 如果存在也是回文，这说明到达当前位置时的最长回文，最多比之前的最长回文多 2 个字符，所以每次我们在位置 i，可以只判断：
s[i-max_len:i+1]（长度为 max_len+1）是否为回文s[i-max_len-1:i+1]（长度为 max_len+2）是否为回文
即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | class Solution:
def longestPalindrome(self, s: str) -> str:
idx, max_len = 0, 1
for i in range(1, len(s)):
s1 = s[i - max_len : i + 1]
s2 = s[i - max_len - 1 : i + 1]
if i - max_len - 1 >= 0 and s2 == s2[::-1]:
idx, max_len = i, max_len + 2
continue
if i - max_len >= 0 and s1 == s1[::-1]:
idx, max_len = i, max_len + 1
return s[idx - max_len + 1 : idx + 1]
|
