最长回文子串
Longest Palindromic Substring
本机进度仅保存在当前浏览器
题目描述
给你一个字符串 s，找到 s 中最长的回文子串（正读反读相同的连续子串）。
示例：s = "babad"，输出 "bab"（或 "aba"）；s = "cbbd"，输出 "bb"。
解题思路
- 中心扩展法最直观：回文由中心向两侧对称，枚举 2n - 1 个中心（每个字符 + 每对相邻字符间），向两侧扩展记录最长。
- 偶长度回文没有单一字符中心，所以相邻两字符相等也要作为一类中心处理。
- DP 解法 dp[i][j] 表示 s[i..j] 是否回文，转移看 s[i] == s[j] 且内部回文，空间 O(n^2)；中心扩展空间 O(1) 更优。
参考实现
查看参考实现Python · 建议先自行作答
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
best_l, best_r = 0, 0
for i in range(len(s)):
for l, r in (expand(i, i), expand(i, i + 1)):
if r - l > best_r - best_l:
best_l, best_r = l, r
return s[best_l:best_r + 1]