Python Straightforward DP Solution


  • 0
    M

    Idea: We follow the intuition that P(Start, End) == (P(Start + 1, End - 1) and S[Start] == S[End]) and store these results in the DP table. We only need to check to update the max string if we've updated the table.

    class Solution(object):
        def longestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            
            """
            if not s:
                return ""
            n = len(s)
            maxFinal = s[0]
            dp = [[0]*n for _ in range(n)]
            for end in range(n):
                dp[end][end] = 1
                for start in range(end):
                    if (dp[start+1][end-1] == 1 or start + 1 > end - 1) and s[start] == s[end]:
                        dp[start][end] = 1
                        if (end - start + 1) > len(maxFinal):
                            maxFinal = s[start:end+1]
            return maxFinal
    

Log in to reply
 

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