最长回文子串超时错误

Question

这就是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)吗？

Answer 1

您的程序很慢，因为您使用了dict而不是仅仅使用列表。理论上dict的检索时间为O(1)，但实际中却要慢得多。通过删除dict和unneccisary循环，我们能够显著提高程序的速度。

    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秒。