leetcode：5. 最长回文子串【dp + 抓着超时的尾巴】

分析

dp[i][j]表示i到j是否回文
然后特例是dp[i][i] dp[i][i + 1]
其他的dp[i][j] 看 dp[i + 1][j - 1]的值 是否非0
以及s[i] 和 s[j]是否相等

ac code

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # n * n
        # dp[i][j]表示[i, j]的回文长度
        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

总结

二维dp

后续 反向贪心暴力反而更快。。。

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

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

        # n * n
        # dp[i][j]表示[i, j]的回文长度
        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]