leetcode：5. Longest palindrome substring [DP + holding the tail of timeout]

analysis

dp[i][j] Express i To j Whether palindrome
And the special case is dp[i][i] dp[i][i + 1]
Other dp[i][j] see dp[i + 1][j - 1] Value Whether it's not 0
as well as s[i] and s[j] Whether it is equal or not

ac code

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # n * n
        # dp[i][j] Express [i, j] Palindrome length of 
        n = len(s)
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = 1
        
        maxn = 1
        ans = s[0]
        for l in range(2, n + 1):
            for start in range(n - l + 1):
                #print(start, start + l - 1)
                if l == 2:
                    if s[start] == s[start + 1]:
                        dp[start][start + 1] = 2
                    else:
                        dp[start][start + 1] = 0
                else:
                    if s[start] == s[start + l - 1] and dp[start + 1][start + l - 2] > 0:
                        dp[start][start + l - 1] = dp[start + 1][start + l - 2] + 2
                    else:
                        dp[start][start + l - 1] = 0
                if dp[start][start + l - 1] > maxn:
                    maxn = dp[start][start + l - 1]
                    ans = s[start: start + l]
        #print(dp)
        return ans

summary

A two-dimensional dp

follow-up Reverse greedy violence is faster ...

class Solution:
    def longestPalindrome(self, s: str) -> str:

        def check(s):
            return s == s[::-1]

        # n * n
        # dp[i][j] Express [i, j] Palindrome length of 
        n = len(s)

        
        maxn = 1
        ans = s[0]
        for l in range(n, 0, -1):
            for start in range(n - l + 1):
                
                if check(s[start: start + l]) and l > maxn:
                    maxn = l
                    ans = s[start: start + l]
                    return ans
        #print(dp)
        #return ans
        return s[0]