Longest Palindromic Substring DP soln


  • 0
    V

    I keep getting a timeout with this solution but i don't see the issue?

    class Solution(object):
        def palindrome(self,a):
            for i,j in zip(range(len(a)),range(len(a))[::-1]):
                if i > j:
                    break
                if a[i]!=a[j]:
                    return False
            return True
        
        def LCS(self, a,b):
            dp = []
            max_pal = ""
            for i in range(len(a)+1):
                dp.append([0] * (len(a)+1))
            for i in range(1,len(a)+1):
                for j in range(1,len(a)+1):
                    if a[i-1] == b[j-1]:
                        dp[i][j] = 1 + dp[i-1][j-1]
                        word = a[i-dp[i][j]:i]
                        if dp[i][j] > len(max_pal) and self.palindrome(word):
                            max_pal = word
            return max_pal
    
        def longestPalindrome(self, s):
            return self.LCS(s, s[::-1])
            # longest common substring (DP)
    

Log in to reply
 

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