Python(3) DP Solution with explanation


  • 0
    X

    dp[i][j] = True if s[i]...s[j] is a palindrome, otherwise False.
    Therefore: dp[i][j] = dp[i+1][j-1] and (s[i] == s[j])
    The base cases: dp[i][i] = True and dp[i][i-1] = (s[i] == s[i-1])
    tmp is the temporary maximum length of palindromic substrings
    0_1484068002128__D.jpg

    class Solution(object):
        def longestPalindrome(self, s):
            tmp,L,R,length = 0,0,0,len(s)
            dp = [[False for i in range(length)] for j in range(length)]
            for i in range(length):
                dp[i][i] = True
            for i in range(1,length):
                dp[i][i-1] = (s[i] == s[i-1])
            for j in range(1,length):
                for i in range(j):
                    if s[i] == s[j] and dp[i+1][j-1]:
                        dp[i][j] = True
                        if j-i+1 > tmp:
                            tmp = j-i+1
                            L,R = i,j
            return s[L:R+1]
    

Log in to reply
 

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