09、最长回文子串

这个也是面试常考的经典题目，我们一块来看一下

https://leetcode.cn/problems/longest-palindromic-substring/

题目描述

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

示例 1:

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

示例 2:

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

约束条件:

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

什么是回文串？

回文串定义

回文串：正着读和反着读都一样的字符串

示例：
"aba" - 回文串 ✓
"abba" - 回文串 ✓
"abc" - 不是回文串 ✗
"a" - 回文串 ✓（单个字符）

回文串的特点

奇数长度回文串：
"aba" - 中心是 'b'
"racecar" - 中心是 'e'

偶数长度回文串：
"abba" - 中心是 "bb"
"noon" - 中心是 "oo"

关键：回文串以中心对称

方法一：动态规划⭐

DP 思路

dp[i][j] 表示 s[i...j] ，字符串 s，从索引 i 到 索引 j 是否为回文串

状态转移：
if (s[i] == s[j]):
    if (j - i <= 2):  # 长度 <= 3
        dp[i][j] = true // 一定是回文，大家可以思考一下
    else:
        dp[i][j] = dp[i+1][j-1] // 需要看前一个子串是不是回文，
                                // 比如 abba,这里的是s[i] == s[j], 均为 a
                                // 此时 s[i+1] == s[j-1],均为 b 为回文，那 abba 也为回文
else:
    dp[i][j] = false // s[i] != s[j] 那必不是回文

遍历顺序：
按子串长度从小到大遍历

代码实现

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();
        if (n < 2) {
            return s;
        }
        // dp[i][j] 表示 s[i..j] 是否为回文
        vector<vector<bool>> dp(n, vector<bool>(n, false));

        // 所有长度为 1 的子串都是回文
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }

        int maxLen = 1;
        int start = 0;

        // 按长度遍历
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i < n - len + 1; i++) {
                int j = i + len - 1;

                if (s[i] == s[j]) {
                    if (len == 2) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i+1][j-1];
                    }

                    if (dp[i][j] && len > maxLen) {
                        maxLen = len;
                        start = i;
                    }
                }
            }
        }

        return s.substr(start, maxLen);
    }
};

时间复杂度: O(n²)

空间复杂度: O(n²)

方法二：中心扩散⭐⭐（推荐）

中心扩散方法是这个题目的最优解，大家可以学习一下

核心思想

问题转化：

• 原问题：找到字符串中最长的回文子串
• 转化后：回文串的关键特征是中心对称，我们可以枚举所有可能的"中心"，从中心向两边扩散，找到以该中心为基础的最长回文串

为什么要考虑两种中心？

回文串有两种情况：

1. 奇数长度回文串（中心是单个字符）
   示例："aba"
   索引：  0 1 2
   字符：  a b a
          ↑↑↑
         左 中 右
   中心：索引 1（字符 'b'）
   扩散：从 left = 1, right = 1 开始，同一起点

2. 偶数长度回文串（中心是两个字符之间）
   示例："abba"
   索引：  0 1 2 3
   字符：  a b b a
          ↑↑↑↑
        左1 中心 右1
             
   中心：索引 1 和 2 之间（字符 "bb"）
   扩散：从 left = 1, right = 2 开始，不同起点

算法思路：

1. 遍历字符串的每个位置 i（作为潜在的回文中心）
2. 对于每个位置 i，检查两种情况：
   1. 奇数长度：以 i 为中心（left = i, right = i）
   2. 偶数长度：以 i 和 i+1 为中心（left = i , right = i+1）
3. 从中心向两边扩散，找到以该中心为基础的最长回文串
4. 记录所有回文串中最长的那个

算法正确性证明

为什么中心扩散是正确的？

关键洞察：
任何回文串都有一个"中心"，从中心向两边是对称的。

证明：
1. 枚举所有可能的中心（n 个奇数中心 + n-1 个偶数中心）
2. 对于每个中心，找到以它为基础的最长回文串
3. 取所有回文串中最长的

完备性：
- 所有回文串都有且仅有一个中心
- 我们枚举了所有可能的中心（奇数+偶数）
- 因此一定能找到最长回文串

代码实现

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty()) {
            return "";
        }
        int start = 0, maxLen = 0;

        for (int i = 0; i < s.length(); i++) {
            // 奇数长度：以 i 为中心
            int len1 = expandAroundCenter(s, i, i);
            // 偶数长度：以 i, i+1 为中心
            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;
    }
};

时间复杂度: O(n²)

空间复杂度: O(1)