CODEWITHSUNDEEP
pythonstringalgorithmdynamic-programminggreedy
Howard
Howard

Reputation: 1

longest palindromic substring time out error

this is the leetcode problem : Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. My solution is using a dp table where dp[i][j] = length of the longest palindromic substring that begins with s[i] and ends with s[j] inclusive

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]

I wonder why my solution has Time Limit Exceeded error, shouldn't it be O(n^2)?

Upvotes: 0

Views: 358

Answers (1)

WIR3D
WIR3D

Reputation: 532

Your program is slow because you use a dict instead of just using a list. Theoretically the retrieval time of the dict is O(1) but int reality it is a lot slower. By removing the dict and unneccisary loops, we are able to significantly increase the speed of the program.

    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])

This is the faster version. I used a randomly generated 1000 character long string in this case. Your original program took around 2 sec to finish this on my computer whereas the optimized one only took 1 sec.

Upvotes: 1

Related Questions