#5
中等
高频
中心扩展法最长回文子串
这是一道围绕字符串、动态规划展开的高频练习。建议先掌握「中心扩展法」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
字符串
动态规划
题目分析
给你一个字符串，要求找出其中最长的一段回文子串，并返回这段子串。
回文串的特点是正着读和反着读完全一样，比如 aba、abba。
这里强调的是“子串”，所以必须是连续的一段。
一句话概括：
从字符串里找到最长的一段对称连续区间。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：把每个字符和每对相邻字符都当成回文中心，向两边同时扩展寻找最长回文。
推荐代码
推荐解法：中心扩展法
时间复杂度： O(n^2)
空间复杂度： O(1)
核心思路： 把每个字符和每对相邻字符都当成回文中心，向两边同时扩展寻找最长回文。
// 中心扩展法的Java实现
public class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) {
return "";
}
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private int expandAroundCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
--left;
++right;
}
return right - left - 1;
}
}
结构化讲解
面试时怎么讲
开场思路
这题我会用中心扩展法，因为回文本身就是围绕中心对称的。
核心过程
- 枚举每个位置作为奇数中心，再枚举每对相邻位置作为偶数中心。
- 从中心向左右同时扩展，只要字符相等就继续。
- 每次扩展结束后得到一个回文区间，用它更新全局最长答案。
- 最终返回记录下来的最长回文子串。
复杂度总结
时间复杂度 O(n^2)，空间复杂度 O(1)。
面试补一句：这题推荐先讲中心扩展，再补充如果需要也可以用 DP。
核心思路
最长回文子串的关键不是记 DP，而是抓住回文的对称性。每个回文都有中心，中心扩展法直接从这个结构出发，写法更轻。
步骤讲解
1
枚举所有可能的回文中心
每个位置都可能是奇数长度回文的中心，每对相邻位置都可能是偶数长度回文的中心。
为什么这样做：回文长度可能是奇数也可能是偶数，所以两种中心都不能漏。
对应代码提示：expand(i, i); expand(i, i + 1);
2
从中心向两边扩展
只要左右字符相等，就继续向外扩，直到越界或不相等为止。
为什么这样做：回文的定义就是左右对称，所以扩展过程天然正确。
对应代码提示：while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) { ... }
3
实时更新最长区间
每次扩展结束后，拿当前回文长度和已有答案比较，保留更长的那一个。
为什么这样做：所有可能回文都会在某个中心被枚举到，持续维护全局最优即可。
对应代码提示：if (right - left - 1 > end - start) { ... }
易错点
只考虑奇数中心
像 abba 这样的偶数长度回文就会被漏掉。
正确理解：每个位置都要做两次扩展：
(i, i) 和 (i, i + 1)。扩展结束后边界直接拿 left/right
循环退出时 left 和 right 已经越过了真实回文边界。
正确理解：真实长度是
right - left - 1，截取时也要做对应修正。把子序列和子串混淆
这题要求连续子串，不能跳过字符。
正确理解：整个算法都围绕连续中心向两边扩展，不能做不连续选择。
复杂度与适用判断
时间复杂度：O(n^2)
空间复杂度：O(1)
比其他方案更好在哪里：比 DP 写法更短，空间更省，也更适合作为首选面试答案。
适用判断：只要题目围绕回文子串展开，先想“有没有中心可以扩”。
额外提醒
- 奇偶长度回文必须分开处理两个中心模型。
其他语言 / 其他解法
动态规划
算法思路待补充
动态规划
算法思路待补充
时间复杂度：O(n²)
空间复杂度：O(n²)
一句话思路：算法思路待补充
// 动态规划算法的Java实现
public class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2) {
return s;
}
int maxLen = 1;
int begin = 0;
// dp[i][j] 表示 s[i..j] 是否是回文串
boolean[][] dp = new boolean[len][len];
// 初始化：所有长度为 1 的子串都是回文串
for (int i = 0; i < len; i++) {
dp[i][i] = true;
}
char[] charArray = s.toCharArray();
// 递推开始
// 先枚举子串长度
for (int L = 2; L <= len; L++) {
// 枚举左边界，左边界的上限设置可以宽松一些
for (int i = 0; i < len; i++) {
// 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
int j = L + i - 1;
// 如果右边界越界，就可以退出当前循环
if (j >= len) {
break;
}
if (charArray[i] != charArray[j]) {
dp[i][j] = false;
} else {
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
// 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
if (dp[i][j] && j - i + 1 > maxLen) {
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substring(begin, begin + maxLen);
}
}
动画演示
如果你还没完全看懂，可以展开动画演示。
中心扩展法动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
中心扩展法动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
准备就绪 - 输入字符串，然后点击开始
执行过程:
动态规划动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
动态规划动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
准备就绪 - 输入字符串，然后点击开始
执行过程:
动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。