5. 最长回文子串 (Medium)
专题归类： 10-动态规划 LeetCode 链接： https://leetcode.cn/problems/longest-palindromic-substring/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给你一个字符串 s，找到 s 中最长的回文子串。
回文串是指正着读和反着读都一样的字符串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
提示：
- 1 <= s.length <= 1000
- s 仅由数字和英文字母组成
题目详细分析
- 数据范围：长度 <= 1000，O(n²) 的 DP 或中心扩展可以通过。
- 核心约束：子串是连续的（与子序列不同）；回文要求对称。
- 边界条件：长度为 1 时，自身就是回文；长度为 2 时，若两字符相等则为回文。
- 隐藏条件：一个回文去掉首尾字符后仍然是回文——这是区间 DP 的基础。中心扩展法利用回文的对称性效率更高。
小白版直白理解
在一串字符中找一段”正反读都一样”的连续子串。这就像找镜子——如果一段字符左右对称，放面镜子在中间，镜子里外是一样的。比如 “babad” 中的 “bab” 就是对称的。判断是不是回文最简单的方法：掐头去尾后剩下的还是回文，且头尾相等。
解题思路
思路一：中心扩展法（推荐）
核心洞察：回文串一定是对称的，所以每个字符（以及每两个相邻字符之间）都可以作为回文中心，向两边扩展直到不是回文。长度为 n 的字符串有 2n-1 个可能的中心。
def longestPalindrome(s):
def expand(l, r):
"""从中心向两端扩展，返回最长回文的起止下标"""
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
return l + 1, r - 1
start = end = 0
for i in range(len(s)):
# 奇数长度回文中心（一个字符）
l1, r1 = expand(i, i)
# 偶数长度回文中心（两个字符之间）
l2, r2 = expand(i, i + 1)
if r1 - l1 > end - start:
start, end = l1, r1
if r2 - l2 > end - start:
start, end = l2, r2
return s[start:end + 1]思路二：区间 DP
核心洞察：定义 dp[i][j] 表示 s[i..j] 是否为回文串。状态转移：若 s[i]==s[j] 且 s[i+1..j-1] 是回文，则 s[i..j] 也是回文。
DP 五步法：
- dp 定义：
dp[i][j]表示 s[i:j+1] 是否为回文串 - 递推公式：
dp[i][j] = (s[i] == s[j] and (j - i <= 2 or dp[i+1][j-1])) - 初始化：
dp[i][i] = True，长度 2 且相等时dp[i][i+1] = True - 遍历顺序：从下往上 i 递减，从左往右 j 递增（因为 dp[i][j] 依赖 dp[i+1][j-1]）
- 举例验证：s=“babad” → i=3,j=4: s[3]=a,s[4]=d≠, 不成立；i=2,j=4: s[2]=b,s[4]=d≠; i=1,j=3: s[1]=a,s[3]=a=且 j-i=2 → dp[1][3]=T → “aba” ✓
def longestPalindrome(s):
n = len(s)
dp = [[False] * n for _ in range(n)]
start = end = 0
for i in range(n - 1, -1, -1): # 从下往上
for j in range(i, n): # 从左往右
if s[i] == s[j] and (j - i <= 2 or dp[i + 1][j - 1]):
dp[i][j] = True
if j - i > end - start:
start, end = i, j
return s[start:end + 1]思路三：Manacher 算法（O(n) 最优解）
利用回文半径数组和对称性，将时间复杂度降到 O(n)。面试一般不要求，但竞赛中很实用。
def longestPalindrome(s):
# 预处理：插入分隔符，统一奇偶长度
t = '^#' + '#'.join(s) + '#$'
n = len(t)
p = [0] * n # p[i] 表示以 i 为中心的回文半径
center = right = 0
for i in range(1, n - 1):
if i < right:
p[i] = min(p[2 * center - i], right - i)
# 中心扩展
while t[i + p[i] + 1] == t[i - p[i] - 1]:
p[i] += 1
# 更新中心和右边界
if i + p[i] > right:
center, right = i, i + p[i]
# 找到最大半径
max_len, center_idx = max((p[i], i) for i in range(1, n - 1))
start = (center_idx - max_len) // 2
return s[start:start + max_len]易错点
- DP 遍历顺序：必须从下往上（i 递减），因为
dp[i][j]依赖dp[i+1][j-1]。从下往上保证左下角先被计算。 - 中心扩展的数量：n 个字符有 2n-1 个中心（n 个单字符中心 + n-1 个双字符中心）。
- 子串 vs 子序列：本题是子串（连续），区分于回文子序列问题。
- 长度 1 的特殊情况：任何单字符都是回文，直接返回 s 本身。
框架提炼
中心扩展模板：
def expand_from_center(s):
def expand(l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
return l + 1, r - 1
# 遍历所有中心
for i in range(len(s)):
expand(i, i) # 奇数
expand(i, i + 1) # 偶数区间 DP 模板（回文类）：
def palindrome_interval_dp(s):
n = len(s)
dp = [[False] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
for j in range(i, n):
if s[i] == s[j] and (j - i <= 2 or dp[i + 1][j - 1]):
dp[i][j] = True关联题目
- 647-回文子串 — 中心扩展计数，本题的计数版本
- 516-最长回文子序列 — 子序列（不连续），要改用子序列 DP
- 32-最长有效括号 — 子串 DP，区间思想与回文类似