why my dp solution in python got TLE?


  • 0
    S

    Can anyone tell me why this DP solution with complexity O(n^2) got Time Limit Exceed? Thx~~

    
    class Solution(object):
        def longestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            """
            if 0 == len(s):
                return ""
            if 1 == len(s):
                return s
    
            max_len = 1
            max_pld = s[0]
    
            pld = [[True] * len(s)] * 2
            pld = numpy.array(pld)
    
            #print(pld)
            width = 0
            while width < len(s):
                i = len(s) - 1
                #print("pld: {}".format(width & 1))
                while i - width >= 0:
                    #print(s[i - width:i+1])
                    if s[i - width] == s[i]:
                        if width == 1:
                            pld[width & 1][i] = True
                        else:
                            pld[width & 1][i] = pld[width & 1][i - 1]
    
                        if pld[width & 1][i] and (width + 1 > max_len):
                            max_pld = s[i - width : i + 1]
                            max_len = width + 1
                    else:
                        pld[width & 1][i] = False
                    #print(pld)
                    i -= 1
                width += 1
            return max_pld
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.