string - 最长回文子串超时错误

这就是leetcode问题：
给定字符串S，在S中找到最长回文子串，可以假定S的最大长度为1000。
我的解决方案是使用一个dp表，其中
dp[i][j]=以s[i]开头、以s[j]结尾的最长回文子串的长度

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）吗？
谢谢！

最佳答案

你的程序很慢，因为你用的是dict而不是list理论上dict的检索时间是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秒。