本文详解如何通过动态规划优化暴力枚举法，将查找最长回文子串的时间复杂度从 o(n³)（原代码实际为 o(n³)，非题述的 o(n²)）降至 o(n²)，并给出可直接落地的 java 实现与关键避坑提示。
本文详解如何通过动态规划优化暴力枚举法，将查找最长回文子串的时间复杂度从 o(n³)（原代码实际为 o(n³)，非题述的 o(n²)）降至 o(n²)，并给出可直接落地的 java 实现与关键避坑提示。
原始代码存在三重隐式开销：外层双指针嵌套循环（O(n²)）、每次截取子串 substring(i, k)（O(n)）、以及 StringBuilder.reverse() + 字符串比较（O(n)），综合时间复杂度实为 O(n³)，远超题目要求。核心瓶颈在于重复判断相同子串是否为回文——例如 "ababa" 中 "bab" 被多次验证。解决之道是空间换时间：用二维 DP 表缓存子问题结果。
✅ 动态规划解法原理
定义 dp[i][j] 为布尔值，表示子串 s[i..j]（闭区间）是否为回文。状态转移方程如下：
- 若 s[i] != s[j] → dp[i][j] = false
- 若 s[i] == s[j] → dp[i][j] = (j - i
- j - i
- dp[i+1][j-1] 复用已计算的更短子串结果，避免重复计算。
关键实现细节：需按子串长度递增或按 i 逆序、j 正序遍历，确保 dp[i+1][j-1] 在计算 dp[i][j] 前已被填充。
? Java 优化实现（O(n²) 时间 + O(n²) 空间）
public static String longestPalindrome(String s) {
if (s == null || s.length() < 2) return s;
int n = s.length();
boolean[][] dp = new boolean[n][n];
int start = 0, maxLength = 1; // 记录最长回文起始索引和长度
// 单字符均为回文
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
// 按子串长度 L 从小到大遍历（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 + 1][j - 1]) {
dp[i][j] = true;
if (len > maxLength) {
maxLength = len;
start = i;
}
}
}
}
}
return s.substring(start, start + maxLength);
}⚠️ 注意事项与进阶建议
- 空间优化：若仅需长度无需子串内容，可用一维 DP（dp[j] 表示以 j 结尾的最长回文长度），但恢复子串需额外逻辑；
- 边界鲁棒性：原题代码中 str 变量未定义（应为 s），且循环条件 k
- 进一步优化：Manacher 算法可达到 O(n) 时间复杂度，适用于超长字符串场景，但实现复杂度较高，DP 方案在可读性与性能间取得最佳平衡；
- 测试验证：务必用边界用例测试——空串、单字符、全相同字符（如 "aaaa"）、无回文（如 "abcde"）——确保 dp 初始化与状态转移无遗漏。
通过动态规划消除重复计算，该方案将时间复杂度稳定控制在 O(n²)，内存访问局部性良好，是工程实践中最推荐的回文子串求解范式。
