如何在 JavaScript 字符串中找到最长的回文子字符串？
在字符串处理问题中，回文字符串（Palindrome） 是一种非常经典的模式：一个字符串如果正着读和反着读完全一样，它就是回文字符串，例如 'racecar' 或 'abba'。
在实际开发中，我们经常需要找到一个字符串中最长的回文子字符串（Longest Palindromic Substring），这不仅考验我们的算法能力，也训练我们对于双指针、中心扩展等技术的掌握。
⚠ 本文不涉及 Manacher 算法（最优 O(n) 解决方案），而是注重于常见算法思维和实战技巧的掌握。
🔍 一、什么是回文字符串？
判断一个字符串是否是回文非常简单。可以直接反转它然后与原始字符串进行比较：
const isPalindrome = str => {
const reversed = str.split('').reverse().join('');
return str === reversed;
};
isPalindrome('racecar'); // true
isPalindrome('abba'); // true
isPalindrome('hello'); // false
🧨 二、暴力破解法（Brute Force）
最直观的方式是穷举所有可能的子字符串，然后依次判断它们是否是回文，保留其中最长的那一个。
实现思路：
- 使用两个指针枚举所有子串。
- 检查是否为回文。
- 更新最长结果。
const longestPalindrome = str => {
let best = { length: 0, value: '' };
for (let l = 0; l < str.length; l++)
for (let r = l + best.length; r < str.length; r++) {
const current = { length: r - l, value: str.slice(l, r + 1) };
if (!isPalindrome(current.value)) continue;
if (current.length < best.length) continue;
best = current;
}
return best.value;
};
longestPalindrome('babad'); // 输出 'bab' 或 'aba'
longestPalindrome('cbbd'); // 输出 'bb'
复杂度分析：
- 时间复杂度：
O(n^3) - 空间复杂度：
O(n)（字符串切片时）
❗暴力法虽然直观，但效率非常低，无法应对大规模数据。
💡 三、中心扩展法（Expand Around Center）
我们可以将每个字符（甚至字符间的空隙）作为“回文中心”，从中心向两边扩展，查找最大长度的回文。
回文扩展核心函数：
const expandAroundCenter = (str, left, right) => {
while (left >= 0 && right < str.length && str[left] === str[right]) {
left--;
right++;
}
return {
left: left + 1,
right: right - 1,
length: right - left - 1
};
};
判断字符串是否为回文：
const isPalindrome = str => {
const centerPoints = (str.length % 2 === 0)
? [str.length / 2 - 1, str.length / 2]
: [Math.floor(str.length / 2), Math.floor(str.length / 2)];
const maxPalindrome = expandAroundCenter(str, ...centerPoints);
return maxPalindrome.length === str.length;
};
🚀 四、最终高效实现（推荐方法）
将中心扩展方法应用到字符串的每一个位置，以捕获最长的回文子串。
const expandAroundCenter = (str, left, right) => {
while (left >= 0 && right < str.length && str[left] === str[right]) {
left--;
right++;
}
return { left: left + 1, right: right - 1, length: right - left - 1 };
};
const longestPalindrome = str => {
let best = { left: 0, right: 0, length: 0 };
for (let i = 0; i < str.length; i++) {
const odd = expandAroundCenter(str, i, i);
const even = expandAroundCenter(str, i, i + 1);
const current = odd.length > even.length ? odd : even;
if (current.length > best.length) best = current;
}
return str.slice(best.left, best.right + 1);
};
longestPalindrome('babad'); // 输出 'bab' 或 'aba'
longestPalindrome('cbbd'); // 输出 'bb'
复杂度分析：
- 时间复杂度：
O(n^2) - 空间复杂度：
O(1)
🧠 五、总结与启发
我们一步步从最基础的暴力破解，优化到基于中心扩展的高效解法。虽然这并非理论上的最优（Manacher 算法可达到 O(n)），但在实际开发中已足够高效且易于实现。
技术要点回顾：
- 双指针技巧 在字符串问题中极其重要。
- 从中心扩展法 是解决对称性问题的通用思路。
- 不要一开始就追求最优算法，先实现可行解再逐步优化。