最长回文子串
mid
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
1
2
3
| 输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
|
示例 2：
1
2
| 输入：s = "cbbd"
输出："bb"
|
中心扩散法
从每一个位置出发，向两边扩散即可。遇到不是回文的时候结束。
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
| func longestPalindrome(s string) string {
var maxLen, maxLeftIndex int = 0, 0
for i := 0; i < len(s); i++ {
leftIndex := i
rightIndex := i
// 寻找回文中心相同部分
for leftIndex-1 >= 0 && s[leftIndex-1] == s[i] {
// 往左扩散 直到遇到与i不相等的字符为止
leftIndex--
}
for rightIndex+1 < len(s) && s[rightIndex+1] == s[i] {
// 往右扩散 直到遇到与i不相等的字符为止
rightIndex++
}
// 左右扩散
for leftIndex-1 >= 0 && rightIndex+1 < len(s) && s[leftIndex-1] == s[rightIndex+1] {
leftIndex--
rightIndex++
}
if rightIndex-leftIndex+1 > maxLen {
maxLen = rightIndex - leftIndex + 1
maxLeftIndex = leftIndex
}
}
return s[maxLeftIndex : maxLeftIndex+maxLen]
}
|
1
2
3
4
5
6
7
8
9
10
11
| class Solution:
def longestPalindrome(self, s: str) -> str:
maxl,max_len,n = 0,0,len(s)
for i in range(2*n-1):
l,r = i//2,i//2+i%2
while l>=0 and r < n and s[l]==s[r]:
if r-l+1>max_len:
maxl,max_len = l,r-l+1
l-=1
r+=1
return s[maxl:maxl+max_len]
|
