.jpg)
765 字
4 分钟
最长回文子串
.png)
题目描述
给你一个字符串 s，找到 s 中最长的回文子串。
解题思路
- 中心扩散法：
- 遍历每个字符和字符间位置作为中心点
- 向左右同时扩展判断回文性质
- 双中心处理：
- 考虑奇偶长度：单字符中心（奇）和双字符中心（偶）
- 确保覆盖所有可能回文串类型
- 边界维护：
- 记录当前最长回文子串起始位置和长度
- 每次扩展成功则更新最大值
- 提前终止优化：
- 剩余扩展空间不足时提前终止
- 减少无效扩展操作
关键洞察
- 中心点选择：
- 2n-1个中心点（n个字符+n-1个间隙）
- 避免遗漏偶数长度回文
- 对称性利用：
- 利用回文左右对称特性
- 减少重复判断次数
- 实时更新机制：
- 每次成功扩展立即更新最大值
- 避免存储中间结果
- 时间复杂度平衡：
- 优于暴力法的O(n³)
- 空间复杂度最低
复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 优势 |
|---|---|---|---|
| 中心扩散法 | O(n²) | O(1) | 实现简单，空间最优 |
| 动态规划 | O(n²) | O(n²) | 状态清晰，可存储所有解 |
| Manacher | O(n) | O(n) | 理论最优，实现复杂 |
代码实现
中心扩展算法
var longestPalindrome = function (s) { if (!s || s.length === 0) return ''; const n = s.length;
let start = 0, maxLen = 1; // 至少一个字符的回文
const expandAroundCenter = (left, right) => { while (left >= 0 && right < n && s[left] === s[right]) { left--; right++; } // 返回实际回文长度 return right - left - 1; };
for (let i = 0; i < n; i++) { // 如果剩余长度不足当前最大回文长度的一半，提前终止 if (i >= n - Math.floor(maxLen / 2)) break;
const len1 = expandAroundCenter(i, i); // 奇数长度回文 const len2 = expandAroundCenter(i, i + 1); // 偶数长度回文 const currMax = Math.max(len1, len2);
if (currMax > maxLen) { maxLen = currMax; // 计算回文起始位置 (i - (maxLen-1)/2) 向下取整 start = i - Math.floor((maxLen - 1) / 2); } }
return s.substring(start, start + maxLen);};DP 动态规划
const longestPalindrome = (s) => { const n = s.length; const dp = Array(n).fill(false).map(() => Array(n).fill(false)); let maxStr = "";
// 所有单字符都是回文 for (let i = 0; i < n; i++) { dp[i][i] = true; maxStr = s[i]; }
for (let len = 2; len <= n; len++) { for (let start = 0; start <= n - len; start++) { const end = start + len - 1; // 首尾相同 && (长度2或中间是回文) if (s[start] === s[end] && (len === 2 || dp[start+1][end-1])) { dp[start][end] = true; if (len > maxStr.length) { maxStr = s.substring(start, end + 1); } } } } return maxStr;};实际应用场景
- DNA序列分析：寻找基因序列中的回文结构（限制酶识别位点）`
- 数据压缩：利用回文特性优化重复模式压缩`
- 欺诈检测：检测镜像对称的异常支付模式`
- 密码学：构造回文结构的加密密钥`