What's wrong with my DP solution?


  • 0
    H

    I'm hitting the time limit on long inputs, but I think I'm following the idea mentioned in the solution:

    class Solution(object):
    def is_palindrome(self, P, s, i, j):
    # Base Case 1: One character string.
    if i == j:
    return P[i][j]

        # Base Case 2: Two-character string.
        if i == j-1:
            P[i][j] = (s[i] == s[j])
            return P[i][j]
    
        if s[i] != s[j]:
            P[i][j] = False
            return False
    
        if P[i][j] is not None:
            return P[i][j]
    
        result = self.is_palindrome(P, s, i+1, j-1)
        P[i][j] = result
    
        #print(P)
    
        return result
    
    
    def longestPalindrome(self, s):
        P = [[None] * len(s) for x in range(len(s))]
    
        for i in range(len(s)):
            P[i][i] = 1
    
        longest_pal = ""
    
        for i in range(len(s)):
            for j in range(i, len(s)):
                substr = s[i:j+1]
                if self.is_palindrome(P, s, i, j) and len(substr) > len(longest_pal):
                    longest_pal = substr
    
        return longest_pal

Log in to reply
 

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