Python Dynamic Programming solution but exceeds Time Limit, please tell me how to improve.


  • 0
    1

    '''

    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        l = len(s)
        p = [[True] * l for x in range(l)]
        t = 0
        max = 0
        ri = 0
        rj = 0
        for j in range(l):
            for i in range(l - j):
                if t == 1:
                    p[i][i + t] = (s[i] == s[i + t]) 
                elif t >= 2:
                    p[i][i + t] = p[i + 1][ i + t - 1] and (s[i] == s[i + t])
                if p[i][i + t] and t + 1 > max:
                    max = t + 1
                    ri = i
                    rj = i + t
            t += 1
        return s[ri:(rj + 1)]
    

    '''
    My algorithm is the same with the approach #3 and I think there is no logical error, but it turns out it exceeds the time limit, I have tried multiple ways to improve the speed but still in vain, can anyone help me handle it?


  • 0
    A

    you don't have to check every case in the loop.
    When you know 'ab' is not a palindrome, then every string centered on 'ab', for example 'cabc' and 'xaby', is not a palindrome. You can then move on to next center. this would help trim a large part of the problem space.


Log in to reply
 

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