问题链接

5.最长回文子串

问题描述

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

示例 1：

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

示例 2：

输入：s = “cbbd”
输出：“bb”

提示：

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

问题解答

一、核心概念回顾

回文串：正读和反读一致的字符串（如 “bab”、“bb”），其核心特性是「以中心为轴对称」。

• 奇数长度回文串：中心是单个字符（如 “bab” 的中心是 ‘a’）；
• 偶数长度回文串：中心是两个相邻字符（如 “bb” 的中心是两个 ‘b’ 之间）。

二、解法一：中心扩散法（推荐）

思路

1. 遍历所有可能的中心：字符串长度为 n 时，有 2n-1 个中心（n 个单个字符中心 + n-1 个两个字符中心）；
2. 向左右扩散验证：对每个中心，左右指针 left 和 right 初始指向中心，若 s[left] == s[right] 则继续扩散，否则停止；
3. 记录最长回文：每次扩散后，若当前回文长度大于历史最大值，更新最长回文的「起始位置」和「长度」。

代码实现

class Solution {
    // 记录最长回文子串的起始位置和长度（全局变量避免方法间传参）
    private int start = 0;
    private int maxLen = 0;

    public String longestPalindrome(String s) {
        int n = s.length();
        // 边界条件：空串或长度为1的串，自身就是最长回文
        if (n < 2) {
            return s;
        }

        // 遍历所有可能的中心，分别处理奇数和偶数长度回文
        for (int i = 0; i < n; i++) {
            expandCenter(s, i, i);   // 奇数长度：中心是单个字符 s[i]
            expandCenter(s, i, i+1); // 偶数长度：中心是 s[i] 和 s[i+1]
        }

        // 根据起始位置和长度截取最长回文子串
        return s.substring(start, start + maxLen);
    }

    /**
     * 辅助方法：从中心向左右扩散，验证回文并更新最长回文信息
     * @param s 原字符串
     * @param left 左指针（初始指向中心左侧）
     * @param right 右指针（初始指向中心右侧）
     */
    private void expandCenter(String s, int left, int right) {
        // 扩散条件：指针不越界 + 左右字符相等
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            // 计算当前回文长度
            int currentLen = right - left + 1;
            // 若当前长度更大，更新最长回文的起始位置和长度
            if (currentLen > maxLen) {
                maxLen = currentLen;
                start = left; // 起始位置是左指针（因为扩散是从中心向外）
            }
            // 继续向左右扩散
            left--;
            right++;
        }
    }
}

复杂度分析

• 时间复杂度：O(n²)，每个中心最多扩散 O(n) 次，共 2n-1 个中心；
• 空间复杂度：O(1)，仅用常量变量存储起始位置和长度，无额外空间开销。

三、解法二：动态规划法

思路

1. 定义 DP 数组：dp[i][j] 表示字符串 s 中从索引 i 到 j（左闭右闭）的子串是否为回文串；
2. 递推公式：
   • 若 s[i] != s[j]：dp[i][j] = false（两端字符不同，不可能是回文）；
   • 若 s[i] == s[j]：
     • 情况 1：j - i <= 1（子串长度 ≤ 2，如 “a”、“aa”），直接为回文，dp[i][j] = true；
     • 情况 2：j - i > 1（子串长度 > 2），需依赖内层子串 dp[i+1][j-1]（若内层是回文，则外层也是回文）；
3. 遍历顺序：从「下到上、从左到右」遍历（因为 dp[i][j] 依赖 dp[i+1][j-1]，需先计算内层子串）；
4. 记录最长回文：每次 dp[i][j] = true 时，判断长度是否超过历史最大值，更新起始位置和长度。

代码实现

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n < 2) {
            return s;
        }

        // 1. 初始化 DP 数组：dp[i][j] 表示 s[i..j] 是否为回文串
        boolean[][] dp = new boolean[n][n];
        // 单个字符一定是回文，初始化对角线（i == j）
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }

        // 记录最长回文子串的起始位置和长度
        int start = 0;
        int maxLen = 1; // 初始最长长度为1（单个字符）

        // 2. 遍历 DP 数组：从下到上（i 从 n-2 到 0），从左到右（j 从 i+1 到 n-1）
        // 原因：dp[i][j] 依赖 dp[i+1][j-1]，需先计算 i+1 行（更靠下的行）
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                // 递推公式：判断 s[i] 和 s[j] 是否相等，再分情况处理
                if (s.charAt(i) == s.charAt(j)) {
                    // 子串长度 ≤ 2（j - i == 1，如 "aa"），直接为回文
                    if (j - i == 1) {
                        dp[i][j] = true;
                    } else {
                        // 子串长度 > 2，依赖内层子串 dp[i+1][j-1]
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                // 若当前子串是回文，且长度更大，更新最长回文信息
                if (dp[i][j]) {
                    int currentLen = j - i + 1;
                    if (currentLen > maxLen) {
                        maxLen = currentLen;
                        start = i;
                    }
                }
            }
        }

        // 截取最长回文子串
        return s.substring(start, start + maxLen);
    }
}

复杂度分析

• 时间复杂度：O(n²)，需遍历 n×n 的 DP 数组；
• 空间复杂度：O(n²)，需存储 n×n 的布尔型 DP 数组。

四、两种解法对比

解法	时间复杂度	空间复杂度	优点	缺点
中心扩散法	O(n²)	O(1)	空间最优，实现简单	无明显缺点
动态规划法	O(n²)	O(n²)	思路直观，可复用子问题结果	空间开销较大，适合小字符串

实际开发中优先选择中心扩散法（空间更优，代码更简洁）；若需理解动态规划的子问题思想，可学习动态规划法。