Medium

题目描述

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

示例 1：

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

示例 2：

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

提示：

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

思考提示：

  • 如何重用之前计算的回文来计算更大的回文？
  • 如果 “aba” 是回文，那么 “xabax” 是回文吗？类似地，“xabay” 是回文吗？
  • 复杂度提示：如果我们使用暴力方法检查每个起始和结束位置的子串是否为回文，我们有 O(n²) 个起始-结束对和 O(n) 次回文检查。我们能否通过重用之前的计算将回文检查的时间复杂度降低到 O(1)？

解题思路

解题思路

这道题有三种主要解法：

1. 中心扩展法（推荐）

最直观的思路是从每个可能的中心点向两边扩展，检查能形成的最长回文串。需要考虑两种情况：

  • 奇数长度回文：以单个字符为中心
  • 偶数长度回文：以两个相同字符之间为中心

对于每个中心点，向两边扩展直到字符不匹配或到达边界，记录最长的回文串。

2. 动态规划

使用二维数组 dp[i][j] 表示子串 s[i...j] 是否为回文。状态转移方程：

  • 当 s[i] == s[j] 且 dp[i+1][j-1] 为真时，dp[i][j] 为真
  • 边界条件：单个字符和相邻相同字符都是回文

3. Manacher算法

时间复杂度 O(n) 的专门算法，通过预处理和利用回文的对称性质来避免重复计算。

考虑到题目规模（n ≤ 1000）和代码简洁性，中心扩展法是最佳选择，既高效又易于理解和实现。

代码实现

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty()) return "";
        
        int start = 0, maxLen = 1;
        
        for (int i = 0; i < s.length(); i++) {
            // 奇数长度回文
            int len1 = expandAroundCenter(s, i, i);
            // 偶数长度回文
            int len2 = expandAroundCenter(s, i, i + 1);
            
            int len = max(len1, len2);
            if (len > maxLen) {
                maxLen = len;
                start = i - (len - 1) / 2;
            }
        }
        
        return s.substr(start, maxLen);
    }
    
private:
    int expandAroundCenter(string s, int left, int right) {
        while (left >= 0 && right < s.length() && s[left] == s[right]) {
            left--;
            right++;
        }
        return right - left - 1;
    }
};

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""
        
        start = 0
        max_len = 1
        
        def expand_around_center(left: int, right: int) -> int:
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return right - left - 1
        
        for i in range(len(s)):
            # 奇数长度回文
            len1 = expand_around_center(i, i)
            # 偶数长度回文
            len2 = expand_around_center(i, i + 1)
            
            length = max(len1, len2)
            if length > max_len:
                max_len = length
                start = i - (length - 1) // 2
        
        return s[start:start + max_len]

public class Solution {
    public string LongestPalindrome(string s) {
        if (string.IsNullOrEmpty(s)) return "";
        
        int start = 0, maxLen = 1;
        
        for (int i = 0; i < s.Length; i++) {
            // 奇数长度回文
            int len1 = ExpandAroundCenter(s, i, i);
            // 偶数长度回文
            int len2 = ExpandAroundCenter(s, i, i + 1);
            
            int len = Math.Max(len1, len2);
            if (len > maxLen) {
                maxLen = len;
                start = i - (len - 1) / 2;
            }
        }
        
        return s.Substring(start, maxLen);
    }
    
    private int ExpandAroundCenter(string s, int left, int right) {
        while (left >= 0 && right < s.Length && s[left] == s[right]) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

var longestPalindrome = function(s) {
    if (!s) return "";
    
    let start = 0, maxLen = 1;
    
    function expandAroundCenter(left, right) {
        while (left >= 0 && right < s.length && s[left]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
中心扩展法O(n²)O(1)
动态规划O(n²)O(n²)
Manacher算法O(n)O(n)

说明：

  • 中心扩展法：遍历每个中心点 O(n)，每次扩展最坏 O(n)，总体 O(n²)
  • 动态规划：双重循环填充 dp 表，需要 O(n²) 的额外空间
  • Manacher算法：线性时间复杂度，但实现较复杂

对于此题规模，推荐使用中心扩展法，代码简洁且空间复杂度最优。

相关题目