【LeetCode】5. Longest Palindromic Substring

1 subject

This question is similar to one , It is also related to palindromes .

2 thought

dp Related questions

• dp[i,j] Express s[i,j] Is it a palindrome string
• On the basis of the above, we only need to judge dp[i+1,j+1] Whether it is a palindrome string , So we have to recurse .
• Finally double for Loop through the longest string

3 Code

class Solution:
    def longestPalindrome(self, s: str) -> str:
        dp = [[0]*len(s) for i in range(len(s))]
        n = len(s)
        for i in range(n):
            dp[i][i] = 1 #  Itself is a palindrome string 
        for span in range(2,n+1): #  Interval length from 2 Start 
            for left in range(0,n-span+1):                
                right = left+span -1
                if s[left] == s[right]: #  If two characters are equal 
                    if left +1 == right:
                        dp[left][right] = 1
                    elif dp[left+1][right-1] :
                        dp[left][right] = 1        
        res = s[0]
        max_len = 1
        for i in range(n):
            for j in range(i+1,n):
                if dp[i][j] == 1:
                    if j-i+1 > max_len:
                        res = s[i:j+1]
                        max_len = j-i+1
        # print(dp)
        return res