如何求解LeetCode第5题——最长回文子串的算法实现？
- 内容介绍
- 文章标签
- 相关推荐
本文共计576个文字，预计阅读时间需要3分钟。
我的程序：pythonclass Solution(object): def longestPalindrome(self, s): if s==: return if len(s)==1: return s res=[] for i in range(len(s)): c=s[i].count(s[i]) if c !=1: b=s[:i-1].rindex(s[i]) res.append(s[b+1:i+1]) return max(res, key=len)
我的程序：
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if s==‘‘:
return ‘‘
if len(s)==1:
return s
res=[]
for i in range(len(s)):
c=s[i:].count(s[i])
if c !=1:
b=s[::-1].index(s[i])
j=len(s)-b-1
if s[i:j+1]==s[i:j+1][::-1] and i!=j:
res.append(s[i:j+1])
else:
c-=1
t=s[i:j]
if len(t)==2:
if t[0]==t[1]:
res.append(t)
break
else:
break
b=t[::-1].index(t[0])
j=len(t)-b-1
if t[:j+1]==t[:j+1][::-1] and j!=0:
res.append(t[:j+1])
c-=1
while c>1:
t=s[i:i+j]
if len(t)==2:
if t[0]==t[1]:
res.append(t)
break
else:
break
b=t[::-1].index(t[0])
j=len(t)-b-1
if t[:j+1]==t[:j+1][::-1] and j!=0:
res.append(t[:j+1])
c-=1
if len(res)==0:
return s[0]
if len(res)==1:
return res[0]
m=max(len(res[i]) for i in range(len(res)))
for i in range(len(res)):
if len(res[i])==m:
return res[i]
执行用时 :2192 ms, 在所有Python提交中击败了50.51%的用户
内存消耗 :115.1 MB, 在所有Python提交中击败了5.06%的用户
虽然好不容易用俩小时左右做出来了，但是感觉还是有地方很啰嗦。
执行用时为 20 ms 的范例
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if len(s) < 2 or s == s[::-1]:
return s
length = 1 even_medium = 0 even_left = 0 for i in range(len(s) - 1): if i - even_left >= 0 and s[i - even_left] == s[i + 1]: substring = s[i - even_left: i + 2] if substring == substring[: : -1]: even_medium = i length = even_left + 2 even_left = even_left + 2 odd_medium = 0 half = (length + 1) // 2 odd_left = (length + 1) // 2 for j in range(half, len(s) - half): if j - odd_left >= 0 and s[j - odd_left] == s[j + half]: substring = s[j - odd_left: j + half + 1] if substring == substring[: : -1]: odd_medium = j length = odd_left + half + 1 odd_left = odd_left + 2 if length % 2 == 0: return s[even_medium + 2 - length: even_medium + 2] else: if length == 1: return s[0] else: return s[odd_medium + half + 1 - length: odd_medium + half + 1]
分析改进：
将我的程序里面的
if s==‘‘: return ‘‘ if len(s)==1: return s
换成：
if len(s) < 2 or s == s[::-1]: return s
其他的还没仔细看。。。。
——2019.10.11
本文共计576个文字，预计阅读时间需要3分钟。
我的程序：pythonclass Solution(object): def longestPalindrome(self, s): if s==: return if len(s)==1: return s res=[] for i in range(len(s)): c=s[i].count(s[i]) if c !=1: b=s[:i-1].rindex(s[i]) res.append(s[b+1:i+1]) return max(res, key=len)
我的程序：
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if s==‘‘:
return ‘‘
if len(s)==1:
return s
res=[]
for i in range(len(s)):
c=s[i:].count(s[i])
if c !=1:
b=s[::-1].index(s[i])
j=len(s)-b-1
if s[i:j+1]==s[i:j+1][::-1] and i!=j:
res.append(s[i:j+1])
else:
c-=1
t=s[i:j]
if len(t)==2:
if t[0]==t[1]:
res.append(t)
break
else:
break
b=t[::-1].index(t[0])
j=len(t)-b-1
if t[:j+1]==t[:j+1][::-1] and j!=0:
res.append(t[:j+1])
c-=1
while c>1:
t=s[i:i+j]
if len(t)==2:
if t[0]==t[1]:
res.append(t)
break
else:
break
b=t[::-1].index(t[0])
j=len(t)-b-1
if t[:j+1]==t[:j+1][::-1] and j!=0:
res.append(t[:j+1])
c-=1
if len(res)==0:
return s[0]
if len(res)==1:
return res[0]
m=max(len(res[i]) for i in range(len(res)))
for i in range(len(res)):
if len(res[i])==m:
return res[i]
执行用时 :2192 ms, 在所有Python提交中击败了50.51%的用户
内存消耗 :115.1 MB, 在所有Python提交中击败了5.06%的用户
虽然好不容易用俩小时左右做出来了，但是感觉还是有地方很啰嗦。
执行用时为 20 ms 的范例
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if len(s) < 2 or s == s[::-1]:
return s
length = 1 even_medium = 0 even_left = 0 for i in range(len(s) - 1): if i - even_left >= 0 and s[i - even_left] == s[i + 1]: substring = s[i - even_left: i + 2] if substring == substring[: : -1]: even_medium = i length = even_left + 2 even_left = even_left + 2 odd_medium = 0 half = (length + 1) // 2 odd_left = (length + 1) // 2 for j in range(half, len(s) - half): if j - odd_left >= 0 and s[j - odd_left] == s[j + half]: substring = s[j - odd_left: j + half + 1] if substring == substring[: : -1]: odd_medium = j length = odd_left + half + 1 odd_left = odd_left + 2 if length % 2 == 0: return s[even_medium + 2 - length: even_medium + 2] else: if length == 1: return s[0] else: return s[odd_medium + half + 1 - length: odd_medium + half + 1]
分析改进：
将我的程序里面的
if s==‘‘: return ‘‘ if len(s)==1: return s
换成：
if len(s) < 2 or s == s[::-1]: return s
其他的还没仔细看。。。。
——2019.10.11