参考链接：

https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/https://leetcode-cn.com/problems/longest-palindromic-substring

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: “babad” 输出: “bab” 注意: “aba” 也是一个有效答案。

示例 2：

输入: “cbbd” 输出: “bb”

回文字符串

如果一个字符串从左向右遍历与从右向左遍历得到的结果一样，则称其为回文字符串。单个字符的字符串是最简单的回文字符串。

解法一：动态规划

时间复杂度：$O(n^2)$ 空间复杂度：$O(n^2)$

对于一个子串而言，如果它是回文串，并且长度大于2，那么将它首尾的两个字母去除之后，它仍然是个回文串。 具体地，首先构建一个存储动态规划状态的矩阵$dp$，大小为$n\times n$，每行表示字符串的起始位置$i$，每列表示字符串的长度$l$，所以每个元素的含义为起始位置为$i$且长度为$l$的字符串是否为回文字符串，初始化为False；然后，在遍历所有情况字符串时，可以利用$dp$中存储的状态和首尾两个字符是否相等，实现动态规划。

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

解法二：中心扩展法

时间复杂度：$O(n^2)$ 空间复杂度：$O(1)$ 边界情况即为子串长度为1或2的情况。我们枚举每一种边界情况，并从对应的子串开始不断地向两边扩展。如果两边的字母相同，我们就可以继续扩展。

class Solution: def expandAroundCenter(self, s, left, right): while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 return left + 1, right - 1 def longestPalindrome(self, s: str) -> str: start, end = 0, 0 for i in range(len(s)): left1, right1 = self.expandAroundCenter(s, i, i) left2, right2 = self.expandAroundCenter(s, i, i + 1) if right1 - left1 > end - start: start, end = left1, right1 if right2 - left2 > end - start: start, end = left2, right2 return s[start: end + 1]

解法三：Manacher 算法

时间复杂度：$O(n)$ 空间复杂度：$O(n)$

当在位置$i$开始进行中心拓展时，我们可以先找到$i$关于$j$的对称点$2\ast j-i$。那么如果点$2\ast j-i$的臂长等于$n$，我们就可以知道，点$i$的臂长至少为$min(j+length-i,n)$。那么我们就可以直接跳过$i$到$i+min(j+length-i,n)$这部分，从$i+min(j+length-i,n)+1$开始拓展。

class Solution: def expand(self, s, left, right): while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 return (right - left - 2) // 2 def longestPalindrome(self, s: str) -> str: end, start = -1, 0 s = '#' + '#'.join(list(s)) + '#' arm_len = [] right = -1 j = -1 for i in range(len(s)): if right >= i: i_sym = 2 * j - i min_arm_len = min(arm_len[i_sym], right - i) cur_arm_len = self.expand(s, i - min_arm_len, i + min_arm_len) else: cur_arm_len = self.expand(s, i, i) arm_len.append(cur_arm_len) if i + cur_arm_len > right: j = i right = i + cur_arm_len if 2 * cur_arm_len + 1 > end - start: start = i - cur_arm_len end = i + cur_arm_len return s[start+1:end+1:2]