# 最长回文子串|博客系列

> 本文详细讲解了如何在给定字符串中寻找最长回文子串，包含题目描述、示例、暴力破解等多种解法及代码实现，适合面试和算法学习，帮助读者高效掌握回文子串问题的解决思路。

- 原文：https://feinterview.poetries.top/docs/fe-blog-docs/blog-docs/leetCode/-%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2
- 来源：前端进阶之旅（feinterview.poetries.top）
- 更新：2025.10.25

---

### 题目描述

给定一个字符串 `s`，找到 `s` 中最长的回文子串。你可以假设 `s` 的最大长度为 1000。

**示例 一🌰：**

```javascript
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
```

**示例二🌰：**

```javascript
输入： "aafddfa"
输出： "afddfa"
```

**示例三🌰：**

```javascript
输入： "abda"
输出： "a"
注意： "abda"并不是回文字符串，"abba"才是
```

所谓回文字符串就比如是：“上海自来水来自海上”，正读反读都是一样的。

### 解题思路1

**暴力破解法：**

（不推荐）

1. 将输入的字符串转换为数组；
2. 嵌套两层`for`循环遍历数组，比较每一种情况下的字符串与它的反转字符串是否相同，若是相同则表明它为回文；
3. 比较出长度最长的回文子串。

暴力解决法最容易理解，但是所需的时间复杂度太大，在`leetCode`上允许只通过了一半的测试用例，因此不推荐使用。

### coding1

```javascript
/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    if (!s) return ''
    if (s.length <= 1) return s
    let sArr = s.split(''),
        maxStrs = [],
        currentStrs = [];
    for (let i = 0; i < sArr.length; i++) {
        for (let j = i; j < sArr.length; j++) {
            currentStrs = sArr.slice(i, j + 1)
            if (currentStrs.join('') === currentStrs.reverse().join('')) {
                maxStrs = maxStrs.length > currentStrs.length ? maxStrs : currentStrs
            }
        }
    }
    return maxStrs.join('')
};
```

### 解题思路2

**三、中心扩展法：**

（相对容易理解且效率高）

> 我们观察到回文中心的两侧互为镜像。因此，回文可以从它的中心展开，并且只有 2n−1 个这样的中心。
>
> 为什么中心是2n-1而不是n ? 比如有字符串abcba，这时回文子串是abcba，中心是c；
>
> 又有字符串adccda，这时回文子串是adccda，中心是cc。 
>
> 由此可见中心点既有可能是一个字符，也有可能是两个字符，当中心为一个字符的时候有n个中心，当中心为两个字符的时候有n-1个中心，所以一共有2n-1个中心。

1. 考虑字符串长度为0和1的情况；
2. 考虑字符串长度为2的情况，若为2则判断这个字符串是不是回文字符串；
3. `for`循环字符串，比较第`i`项和第`i+1`项是否相同(`s[i]`是否等于`s[i+1]`)；
4. 若是相同则表示`s[i] + s[i+1]`为偶数的回文中心，因此应该继续比较`i-1`和`i+2`项；比如给定字符串`abba`，`i`为`1`时，我们已经知道了`s[i] + s[i+1]`，此时应该以`bb`为中心向左右进行扩展比较`s[i-1]`和`s[i+2`]项；
5. 若是不同则表示字符串可能是为寄数的回文中心，因此应该以`s[i]`为中心向左右进行扩展比较`s[i-1]`和`s[i+1]`项；
6. 每次`for`循环中比较上面得到的寄数回文字符串和偶数回文字符串，取较长的；
7. 每次`for`循环中比较之前记录下最长的回文字符串和这次的回文字符串，取较长的；
8. `for` 循环之后即可得到最长回文字符串；

中心扩展法的核心就是通过找到回文中心，然后以该中心向左右两边扩展来查找。

*复杂度分析*

时间复杂度：`O(n^2)`，由于围绕中心来扩展回文会耗去 `O(n)` 的时间，所以总的复杂度为 `O(n^2)`

空间复杂度：`O(1)`。

### coding2

```javascript
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function (s) {
    if (!s) return ''
    if (s.length === 1) return s;
    if (s.length === 2) return s[0] === s[1] ? s : s[1];
    let maxStr = '',
        len = s.length;
    for (let i = 0; i < len; i++) {
        let even = '', // 定义偶数中心回文
            odd = ''; // 定义奇数中心回文
        if (s[i] === s[i + 1]) { // 若是偶数中心回文
            let evenIndex = center(s, i - 1, i + 2); // 比较中心的前一项和后一项
            even = s.slice(evenIndex.left, evenIndex.right)
        }
        let oddIndex = center(s, i - 1, i + 1); // 奇数中心回文
        odd = s.slice(oddIndex.left, oddIndex.right);
        let longer = even.length > odd.length ? even : odd; // 比较奇、偶
        maxStr = maxStr.length > longer.length ? maxStr : longer
    }
    return maxStr
}
// 中心扩展
function center(s, left, right) {
    let len = s.length;
    while (left >= 0 && right < len && s[left] === s[right]) {
        left--;
        right++;
    }
    return { left: left + 1, right: right }
}
```
