What's wrong with my DP solution?

  • 0

    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
        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.