nineloong's blog

题目描述

LeetCode 5 — 最长回文子串 (Medium)

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

回文串指的是正着读和反着读一样的字符串，比如 "aba" 和 "bb"。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案，返回任意一个即可。

示例 2：

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

约束：

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

求解思路

判断一个字符串是不是回文，最简单的办法是头尾两个指针往中间走，边走边比，如果全部对上了就是回文。那么要找最长回文子串，暴力思路也很直白：枚举所有子串的起止位置，逐个判断，记录最长的那个。枚举 $O(n^2)$ 个子串，每个子串判断一次要 $O(n)$ ，总共 $O(n^3)$ ，对于 1000 长度的输入显然撑不住。

观察一下回文串的结构，可以发现一个关键性质：如果一个子串是回文，那么掐头去尾之后剩下的部分也一定是回文。反过来也成立——如果较短的内层子串已经是回文，而且外层两边的字符相等，那这个更长的子串就还是回文。比如已知 "bab" 是回文，左边加 a 右边也加 a，得到 "ababa"，仍然是回文。

这个性质引出了三种不同的解题角度。一是动态规划——大回文依赖小回文的结论，大问题的解可以从小问题的解递推出来；二是中心扩展——回文天然关于中心对称，从每个位置向外扩散即可找到以该位置为中心的最长回文；三是 Manacher 算法——在中心扩展的基础上，利用已计算出的回文信息跳过冗余的比较。下面依次展开。

解法一：动态规划

设 dp[i][j] 表示子串 s[i..j] 是否是回文串。可得以下状态转移方程：

$dp[i][j] = dp[i+1][j-1] \ \land \ (s[i] == s[j])$

也就是说，s[i..j] 是回文当且仅当 s[i+1..j-1] 是回文，并且两端新加的字符相等。

填表时要注意顺序：dp[i][j] 依赖它左下方的 dp[i+1][j-1]，所以不能按行或按列顺序填。最自然的做法是按子串长度从小到大遍历——长度为 1 和 2 的子串作为初始条件直接判断，长度 ≥3 的再走递推公式。

边界情况：单个字符一定是回文，dp[i][i] = true；长度为 2 时，只要两个字符相等就是回文。

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n < 2) return s;

        int maxLen = 1;
        int begin = 0;

        // 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;
        }

        // 长度为 2 的子串，两字符相等即为回文
        for (int i = 0; i < n - 1; i++) {
            if (s[i] == s[i + 1]) {
                dp[i][i + 1] = true;
                maxLen = 2;
                begin = i;
            }
        }

        // 长度从 3 开始，按状态转移方程填表
        for (int l = 3; l <= n; l++) {
            for (int i = 0; i + l - 1 < n; i++) {
                int j = i + l - 1;
                if (dp[i + 1][j - 1] && s[i] == s[j]) {
                    dp[i][j] = true;
                    if (l > maxLen) {
                        maxLen = l;
                        begin = i;
                    }
                }
            }
        }
        return s.substr(begin, maxLen);
    }
};

复杂度： 时间 $O(n^2)$ ，两层循环填充二维表的上三角区域；空间 $O(n^2)$ ，需要一个 n × n 的布尔数组。返回结果时 substr 会产生一份副本，也是 $O(n)$ ，不改变整体量级。

解法二：中心扩展

回文串关于中心对称，从中心往两边扩是最直观的判断方式。一个中心往两边逐字符比，比到不相等就停，停止前的位置就是该中心能形成的最长回文。

不过只把每个字符当作中心是不够的，这样只能找到奇数长度的回文，偶数长度的回文中心在两个字符之间的缝隙上，会漏掉。所以每个位置都要考虑两种情况：以当前字符本身为中心（奇数长度），和以当前字符与下一个字符之间的缝隙为中心（偶数长度）。n 个字符加上 n-1 个缝隙，一共 2n-1 个中心点。

expandAroundCenter 函数从中心向两边扩散，返回回文子串的左右边界（闭区间）。每次扩散结束后比较长度，保留最长的那个。

class Solution {
public:
    string longestPalindrome(string s) {
        int start = 0, end = 0;
        for (int i = 0; i < s.size(); ++i) {
            auto [left1, right1] = expandAroundCenter(s, i, i);     // 奇数长度
            auto [left2, right2] = expandAroundCenter(s, i, i + 1); // 偶数长度
            if (right1 - left1 > end - start) {
                start = left1;
                end = right1;
            }
            if (right2 - left2 > end - start) {
                start = left2;
                end = right2;
            }
        }
        return s.substr(start, end - start + 1);
    }

private:
    pair<int, int> expandAroundCenter(const string& s, int left, int right) {
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            --left;
            ++right;
        }
        // while 退出时 left 和 right 已经越过了回文边界，需要回退一步
        return {left + 1, right - 1};
    }
};

复杂度： 时间 $O(n^2)$ ，每个中心最坏向外扩散 $O(n)$ 步，大多数中心扩散不了几步就停了，常数因子很小；空间 $O(1)$ ，只用了常数个变量。

解法三：Manacher 算法

Manacher 算法解决的是一个根本问题：回文判断本质上可以通过中心扩展完成，但相邻中心的扩散范围高度重叠，同一段字符被反复检查。比如 "aaaaa"，第一个 a 为中心时向右扩到了第 5 个位置，第二个 a 为中心时其实不用从头比——它的回文半径很大一部分已经被前一次扩散覆盖了。Manacher 正是利用已经计算过的回文信息，在中心扩展之前先给一个尽可能大的初始半径，跳过那些已知对称的部分，只做必要的扩展。

预处理：统一奇偶长度

回文串有奇数长度和偶数长度两种，分开处理比较麻烦。Manacher 的做法是在原字符串的每个字符前后都插入一个特殊分隔符（通常用 #），再在首尾各加一个哨兵字符（如 ^ 和 $）。比如 "babad" 变成 "^#b#a#b#a#d#$"。

这样做有两个好处：第一，无论原串是奇是偶，变换后每个回文都是奇数长度，中心都落在一个确切的字符上，不再需要分情况讨论；第二，首尾哨兵保证扩展时永远不会越界，省掉了边界检查。

注意变换后的回文半径和原串回文长度有一个精确的对应关系——变换串中以某个字符为中心的回文半径，恰好等于原串中对应回文子串的长度。比如变换串中 #a#b#a#，中心 b 的半径为 3，对应原串回文 "aba" 长度也是 3。这个性质不是巧合，是 # 的插入数量刚好比原字符多 1 带来的必然结果。

核心思想：利用镜像

Manacher 维护两个变量：C 是当前已知右边界最远的回文中心，R 是这个回文的右边界。遍历时对于每个位置 i，分情况处理：

情况一：i 在 R 之外（即 i >= R）。此时 i 没有被任何已知回文覆盖，没法偷懒，只能从半径 0 开始老老实实中心扩展。

情况二：i 在 R 之内（即 i < R）。这里就要用到镜像。i 关于中心 C 的镜像位置是 i_mirror = 2C - i，这三个位置的关系是 ... i_mirror ... C ... i ... R，i_mirror 到 C 的距离等于 C 到 i 的距离。

由于以 C 为中心的大回文内部是对称的，i 附近的字符格局和 i_mirror 附近的字符格局是镜像关系。既然我们之前已经算出了以 i_mirror 为中心的回文半径 P[i_mirror]，那 i 处的回文半径大概率至少和 i_mirror 一样——前提是这个半径不超出 R 的范围。

超出 R 的部分就没法保证了，因为 R 右侧的字符还在未知区域。所以先把 P[i] 初始化为 min(R - i, P[i_mirror])——取镜像半径和到右边界距离中较小的那个。这个初始化值就是可以安全跳过的部分，然后再从这个基础出发继续向外扩展。运气好的时候，P[i_mirror] 本身就小于 R - i，说明以 i_mirror 为中心的回文完全被包在以 C 为中心的大回文内部，根据对称性，i 处也必然形成相同半径的回文，后续扩展一步都走不动，直接跳过；运气差一点，P[i_mirror] 顶到了边界，那初始化之后还得老老实实往外比。

每次扩展完成后，如果新回文的右边界超过了 R，就更新 C = i 和 R = i + P[i]，让这个边界信息惠及后续位置。

遍历过程中维护全局最大半径和对应的中心位置。最后用中心位置和最大半径反推原字符串中的起点和长度即可。

完整代码

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty()) return "";

        // 预处理：插入 # 和首尾哨兵
        string T = "^";
        for (char c : s) {
            T += "#";
            T += c;
        }
        T += "#$";

        int n = T.length();
        vector<int> P(n, 0); // P[i]：以 T[i] 为中心的回文半径
        int C = 0;           // 当前右边界最远的回文中心
        int R = 0;           // 那个回文的右边界
        int maxLen = 0;      // 记录全局最大半径
        int centerIndex = 0; // 对应的中心位置

        // 遍历变换后的字符串（跳过首尾哨兵）
        for (int i = 1; i < n - 1; i++) {
            int i_mirror = 2 * C - i; // i 关于 C 的镜像

            // 如果 i 落在已知回文内部，利用镜像初始化半径
            if (R > i) {
                P[i] = min(R - i, P[i_mirror]);
            }

            // 在初始化基础上继续向外扩展
            while (T[i + 1 + P[i]] == T[i - 1 - P[i]]) {
                P[i]++;
            }

            // 扩展出的右边界超过了 R，更新 C 和 R
            if (i + P[i] > R) {
                C = i;
                R = i + P[i];
            }

            // 更新全局最优
            if (P[i] > maxLen) {
                maxLen = P[i];
                centerIndex = i;
            }
        }

        // 从变换串中心反推原串的起始位置
        int start = (centerIndex - 1 - maxLen) / 2;
        return s.substr(start, maxLen);
    }
};

几个容易困惑的点

关于 P[i] 为什么要初始化为 min(R - i, P[i_mirror]) 而不是直接等于 P[i_mirror]：当 P[i_mirror] 比 R - i 大时，说明 i_mirror 的回文向左超出了大回文的左边界，右边 i 的对应位置只在 [i, R] 范围内有镜像对称的保证，R 右边是什么还不清楚，所以只能初始化为 R - i，剩下的部分靠扩展去检查。

关于最终结果的反推公式 start = (centerIndex - 1 - maxLen) / 2：变换串中中心索引是 centerIndex，回文在变换串中的起始是 centerIndex - maxLen，而这个位置要么落在 # 上要么落在原字符上。以 "babad" 变换为 "^#b#a#b#a#d#$" 为例，最长的回文 "aba" 在变换串中对应 #a#b#a#，中心 b 的索引是 6，半径是 3，反算 (6 - 1 - 3) / 2 = 1，原串中确实是索引 1。这个公式拿几个例子手推一遍就清楚了。

关于首尾哨兵 ^ 和 $：它们的作用是让扩展的 while 循环一定会在边界处停下来，因为 ^ 和 $ 不可能等于任何其他字符。不加哨兵的话需要在 while 条件里额外判断是否越界。这是一种用哨兵换取代码简洁性的常用技巧。

复杂度： 时间 $O(n)$ 。每个字符最多被成功匹配一次（匹配成功就会推动 R 右移，而 R 只会从 0 走到 n），所以内层 while 循环摊到整个遍历上是线性开销；空间 $O(n)$ ，变换后的字符串和 P 数组各为 $O(n)$ 。最后的 substr 同样产生一份 $O(n)$ 的副本。

最长回文子串：从 O(n²) 到 O(n)