【数据结构与算法】力扣 5. 最长回文子串

题目描述

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的 回文子串。

示例 1：

输入： s = "babad"
输出： "bab"
解释： "aba" 同样是符合题意的答案。

示例 2：

输入： s = "cbbd"
输出： "bb"

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

分析解答

最长回文子串：中心扩展法详解 🚀

我们采用 中心扩展法 来解决这个问题。这个方法利用了回文串的对称性质，通过从中心向两边扩展来查找最长的回文子串。

1. 回文字符串的特点

• 回文串是对称的，比如：
  • "aba"（奇数长度，中心是 "b"）
  • "abba"（偶数长度，中心是 "bb"）
• 回文一定有一个中心：
  • 奇数回文：有 1 个中心字符，如 "racecar"（中心是 "e"）。
  • 偶数回文：有 2 个中心字符，如 "abccba"（中心是 "cc"）。

所以，我们可以 从每个字符出发，尝试以它为中心进行扩展，找到最长的回文子串。

2. 中心扩展法的核心思想

1. 遍历字符串 s 中的每个字符 i：

   • 以 s[i] 为中心，扩展找到 奇数长度 的回文。
   • 以 s[i] 和 s[i+1] 为中心，扩展找到 偶数长度 的回文。

2. 如何扩展？

   • 令 left = i，right = i（奇数回文）。
   • 令 left = i，right = i+1（偶数回文）。
   • 在 s[left] === s[right] 时，不断 向两边扩展，直到 s[left] !== s[right] 为止。

3. 记录最长回文的起点 start 和长度 maxLen，更新最大回文子串的范围。

3. 代码详细解析

function longestPalindrome(s) {
    if (s.length <= 1) return s; // 只有 1 个字符或空字符串，直接返回

    let start = 0, maxLen = 0; // 记录最长回文的起点和长度

    // 中心扩展函数，返回最长回文的起点和长度
    function expandAroundCenter(left, right) {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            left--;   // 左边扩展
            right++;  // 右边扩展
        }
        return [left + 1, right - left - 1]; // 起点 (left+1)，长度 (right-left-1)
    }

    for (let i = 0; i < s.length; i++) {
        // 处理奇数长度回文
        let [oddStart, oddLen] = expandAroundCenter(i, i);
        if (oddLen > maxLen) {
            start = oddStart;
            maxLen = oddLen;
        }

        // 处理偶数长度回文
        let [evenStart, evenLen] = expandAroundCenter(i, i + 1);
        if (evenLen > maxLen) {
            start = evenStart;
            maxLen = evenLen;
        }
    }

    return s.substring(start, start + maxLen);
}

4. 代码执行流程解析

我们以 s = "babad" 为例，模拟执行过程：

Step 1: 遍历 s，每个字符作为中心

Step 2: 选出最长回文

• "bab" 和 "aba" 都是长度为 3 的回文。
• maxLen = 3，最终返回 “bab” 或 “aba”（都符合要求）。

5. 复杂度分析

• 时间复杂度：O(n²)
  • 每个字符 i 都会触发一次 expandAroundCenter，最多扩展 O(n) 次，因此总共是 O(n²)。
• 空间复杂度：O(1)
  • 只使用了 start、maxLen 等变量，没有额外数组存储，空间复杂度是 常数级 O(1)。

思路拓展

动态规划 O(n²) 也是可行的，但需要 O(n²) 的额外空间，而 中心扩展法更省空间（O(1)）。

动态规划 vs. 中心扩展