最长回文子串超时错误
最长回文子串超时错误
提问于 2018-06-15 05:55:32
这就是leetcode问题:给定一个字符串s，在s中找到最长的回文子字符串。你可以假设s的最大长度是1000。我的解决方案是使用dp表，其中dpi =最长的回文子字符串的长度，该子字符串以si开头，以sj结束(包括
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
from collections import defaultdict
dp = defaultdict(lambda: defaultdict(int))
for i in range(len(s)):
dp[i][i] = 1
for i in range(len(s)):
for j in range(i):
dp[i][j] = 0
for i in range(len(s)-2,-1,-1):
for j in range(i+1,len(s)):
# print i,j
if s[i] == s[j]:
if dp[i+1][j-1] != 0 or (dp[i+1][j-1] == 0 and i+1 == j):
dp[i][j] = dp[i+1][j-1] + 2
else:
dp[i][j] = 0
ma = 0
for i in dp:
for j in dp[i]:
ma = max(ma,dp[i][j])
for i in dp:
for j in dp[i]:
if ma == dp[i][j]:
return s[i:j+1]我想知道为什么我的解决方案超出了时间限制错误，它不应该是O(n^2)吗？
回答 1
Stack Overflow用户
发布于 2018-06-15 10:50:19
你的程序很慢，因为你使用的是字典而不是列表。理论上，字典的检索时间是O(1)，但实际上要慢得多。通过删除dict和不必要的循环，我们能够显著提高程序的速度。
import datetime
dp = []
s = "2002102312021431021040231111020201133311233024421042231304121241020023142221114230004301243314231230214433111214211314133411004342320014022213111042430444004404311314414200241443301440042103234032030121140001041102303330110233133340432134433210112441424442023312122012402303012311424320243021030201004404000233341240024023144124044404302020410204423323302241442333033201414131324123134403044304322144401024224303321214233130212433144203342422324100041134301121132222001220203130411024402234004321003440112131342041403304201333110022003023302203024304401002123122342411442214213321413143300334244430320213112244342103103204123233312034020241340322132002141410211130244413124101114032043134121044210134141023134243114420112213332140001323102023014003011402012421443222032402233333402044010204113132440133331131221102004121233103312123433211331411321403124131442401414233311420022322231312101043131324112421403332220423134430421023401314111414244401032422411033440022130241432302100314102230341313003040"
print(datetime.datetime.now().strftime('%S.%f')[:-3])
for i in range(len(s)+1):
new =[]
for j in range(len(s)+1):
if i==j:
new.append(1)
else:
new.append(0)
dp.append(new)
ma = 0
res=""
for i in range(len(s) - 2, -1, -1):
for j in range(i + 1, len(s)):
if s[i] == s[j]:
if dp[i + 1][j - 1] != 0 or (dp[i + 1][j - 1] == 0 and i + 1 == j):
dp[i][j] = dp[i + 1][j - 1] + 2
if ma < dp[i][j]:
ma = dp[i][j]
res = s[i:j + 1]
elif i != j:
dp[i][j] = 0
print(res)
print(datetime.datetime.now().strftime('%S.%f')[:-3])这是更快的版本。在本例中，我使用了一个随机生成的1000个字符的字符串。你的原始程序在我的电脑上花了大约2秒才完成，而优化后的程序只用了1秒。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/50866477
复制相关文章
相似问题
腾讯云开发者
