力扣刷题-最长回文子串
问题描述
给你一个字符串 s,找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。
1
2
3
|
输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。
|
1
2
|
输入:s = "cbbd"
输出:"bb"
|
提示:
- 1 <= s.length <= 1000
- s 仅由数字和英文字母组成
代码
- 由于回文串是对称的,所以我们可以枚举所有的中点,再向两侧扩散,时间复杂度为O(n^2)。
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
|
# @lc code=start
class Solution:
def longestPalindrome(self, s: str) -> str:
# @lc code=end
len1 = len(s)
maxlen= 0
maxstr = ""
for i in range(0,len1):
left = i - 1
right = i + 1
while left>0 and right<len1 and s[left]==s[right]:
left-=1
right+=1
if maxlen < (right-left-1):
maxlen = (right-left-1)
maxstr = s[left:right]
left = i
right= i+1
while left>0 and right<len1 and s[left]==s[right]:
left-=1
right+=1
if maxlen < (right-left-1):
maxlen = (right-left-1)
maxstr = s[left:right]
return maxstr
|