最长回文子串

题目描述：
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串

示例：

输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

使用动态规划解决此问题
设dp[i][j]是字符串从i到j是否回文
当s[i]!=s[j]时 => dp[i][j]为false
当s[i]=s[j]时且j-i<3时 => dp[i][j]为true
当s[i]=s[j]时且j-i>=3时 => dp[i+1][j-1]

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n == 0:
            return ""
        
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True
        
        start, max_length = 0, 1
        for i in range(n - 1):
            if s[i] == s[i + 1]:
                dp[i][i + 1] = True
                start = i
                max_length = 2

        for length in range(3, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                if dp[i + 1][j - 1] and s[i] == s[j]:
                    dp[i][j] = True
                    start = i
                    max_length = length
        return s[start:start + max_length]