Time Limit Exceeded - looks super fast when I test on my machine


  • 0
    H
    class Solution(object):
        def longestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            """
            n = len(s)
            if n <= 1:
                return s
            dp = [[False for i in range(n)] for j in range(n)]
            startIdx = 0
            endIdx = 0
            for i in range(n):
                dp[i][i] = True
            for i in range(n-1):
                if s[i] == s[i+1]:
                    dp[i][i+1] = True
                    startIdx = i
                    endIdx = i+1
            maxLength = endIdx - startIdx + 1
            # loop through each row and column and update dp
            for i in range(n-2, -1, -1):
                for j in range(i+2, n):
                    if dp[i+1][j-1] and s[i] == s[j]:
                        dp[i][j] = True
                        if j-i+1 <= maxLength:
                            continue
                        startIdx = i
                        endIdx = j
                        maxLength = j-i+1
            return s[startIdx:(endIdx+1)]

Log in to reply
 

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