题目
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd" 输出："bb"
示例 3：
输入：s = "a" 输出："a"
示例 4：
输入：s = "ac" 输出："a"
解题
方法一：动态规划
class Solution: def longestPalindrome(self, s: str) -> str: n = len(s) dp = [[False] * n for _ in range(n)] ans = "" # 枚举子串的长度 l+1 for l in range(n): # 枚举子串的起始位置 i，这样可以通过 j=i+l 得到子串的结束位置 for i in range(n): j = i + l if j >= len(s): break if l == 0: dp[i][j] = True elif l == 1: dp[i][j] = (s[i] == s[j]) else: dp[i][j] = (dp[i + 1][j - 1] and s[i] == s[j]) if dp[i][j] and l + 1 > len(ans): ans = s[i:j+1] return ans
但是官方的解法超时了。（而且l和1看不太清）
于是将他改一下
class Solution: def longestPalindrome(self, s: str) -> str: n = len(s) if n < 2:return s ###### dp = [[True] * n for _ in range(n)] ######### res = s[0] ####因为间隔直接从1开始了，所以初始res取个长度为1的就行了 for length in range(1,n): ########从1开始 for left in range(n): right = left + length if right >= n: break ######删了一行 elif length == 1: dp[left][right] = (s[left] == s[right]) else: dp[left][right] = dp[left+1][right-1] and (s[left] == s[right]) if dp[left][right] and length + 1 > len(res): res = s[left: right+1] return res
