leetcode-5. 最长回文子串
一、问题描述
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
示例 1:
输入: "babad" 输出: "bab" 注意: "aba"也是一个有效答案。
示例 2:
输入: "cbbd" 输出: "bb"
二、代码和思路
1.首先每次选择一个字母左右遍历寻找最长回文串,每次寻找完将字母标志位k向后移一位
2.寻找最长回文串有两种情况,分别为s[i]==s[i-1]或者s[i]==s[i-2]都可以,需要同时考虑到这两种情况
感觉代码复杂度有点高
class Solution:
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
n=len(s)
if n==0:return ''
if n==1:return s
length=1;return_str=s[0]
if s[0]==s[1]:
length=2
return_str=s[0:2]
i=j=k=2
while i<n:
if s[i]==s[i-1]:
j -= 1
while i<n-1 and j>0 and s[i+1]==s[j-1]:
i += 1
j -= 1
if i-j+1>length:
length=i-j+1
return_str=s[j:i+1]
i=j=k
if s[i]==s[i-2]:
j -= 2
while i<n-1 and j>0 and s[i+1]==s[j-1]:
i += 1
j -= 1
if i-j+1>length:
length=i-j+1
return_str=s[j:i+1]
k += 1
i=j=k
return return_str
三、运行结果
结果不太好