本文详解如何通过动态规划替代暴力枚举，将查找最长回文子串的时间复杂度从原始代码的 o(n³)（实际含 substring + reverse 的隐式开销）显著优化至 o(n²)，并提供可直接落地的 java 实现与关键避坑指南。
本文详解如何通过动态规划替代暴力枚举，将查找最长回文子串的时间复杂度从原始代码的 o(n³)（实际含 substring + reverse 的隐式开销）显著优化至 o(n²)，并提供可直接落地的 java 实现与关键避坑指南。
原始代码存在三重性能瓶颈：
- 双重循环逻辑错误：for (int i = 0, k = 1; ...) 中 k 未重置导致遍历不完整，且边界条件混乱；
- 高频字符串切片与反转：每次 substring() 和 StringBuilder.reverse() 均为 O(L) 操作（L 为子串长度），内层循环中反复执行，使整体复杂度升至 O(n³)；
- 重复计算：对同一子串如 "aba" 的回文判定，在不同外层迭代中被多次执行，缺乏状态复用。
✅ 正确解法：动态规划（DP）优化
核心思想是利用「子问题最优性」：若 s[i...j] 是回文，则必有 s[i] == s[j] 且 s[i+1...j-1] 也是回文（长度 ≥ 2 时）。我们用二维布尔数组 dp[i][j] 表示子串 s.substring(i, j+1) 是否为回文，按长度从小到大或起始位置从后往前递推填充。
以下是高效、健壮的 Java 实现：
public static String longestPalindrome(String s) {
if (s == null || s.length() <= 1) return s;
int n = s.length();
boolean[][] dp = new boolean[n][n];
int start = 0, maxLength = 1; // 至少单字符为回文
// 所有长度为1的子串都是回文
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
// 枚举长度 L 从 2 到 n
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1; // 子串结束索引
if (s.charAt(i) == s.charAt(j)) {
if (len == 2) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
} else {
dp[i][j] = false;
}
// 更新最长回文信息
if (dp[i][j] && len > maxLength) {
start = i;
maxLength = len;
}
}
}
return s.substring(start, start + maxLength);
}⚠️ 关键注意事项
- 初始化必须覆盖所有单字符：dp[i][i] = true 是递推基石，不可省略；
- 遍历顺序决定正确性：按长度递增（或 i 从后往前、j 从 i 往后）确保 dp[i+1][j-1] 在计算 dp[i][j] 前已被求解；
- 避免 substring + reverse：原方法中 sb.reverse().toString() 不仅耗时，还创建大量临时对象，GC 压力陡增；DP 方案全程仅用字符比较和布尔数组查表；
- 边界处理：空串、单字符、全相同字符等 corner case 需显式覆盖，本实现已兼顾；
- 空间优化提示：若仅需长度无需子串内容，可用滚动数组将空间降至 O(n)；但获取具体子串时二维数组更直观。
✅ 复杂度对比总结
| 方法 | 时间复杂度 | 空间复杂度 | 实际性能表现 |
|---|---|---|---|
| 原始暴力代码 | O(n³) | O(n) | n=1000 时可能超时/卡顿 |
| 动态规划 | O(n²) | O(n²) | n=2000 仍稳定毫秒级响应 |
该方案不仅满足时间要求，代码结构清晰、可读性强，且易于扩展（如统计回文子串总数、支持修改后查询等）。掌握此 DP 范式，可迁移解决“最长回文子序列”“回文分割”等同类问题。
