LeetCode 5. 最长回文子串

◎

本节目标

枚举奇偶中心并向两侧扩展，得到最长连续回文子串。

题意与约束

返回字符串中的最长连续回文子串；长度为一的字符本身就是回文。

第一反应与重复子问题

区间 DP 可由更短内部区间判断，但本题还可比较中心扩展：每个回文都有一个奇或偶中心。

状态定义与转移推导

固定中心后向两侧扩展，s[left] == s[right] 才能继续；每次成功扩展就比较当前长度与最优答案。

正确性依据

任意回文子串都有唯一的中心类型，枚举全部中心并扩展到不能扩展时，必会检查到全局最长回文。

样例执行过程

abcbad 以中间 c 为中心依次得到 c、bcb、abcba，继续扩展时两端越界，因此记录长度五。

代码实现

C++

C++17

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        int n = static_cast<int>(s.size());
        int bestLeft = 0;
        int bestLength = 0;
        for (int center = 0; center < n; center++) {
            for (int left = center, right = center; left >= 0 && right < n && s[left] == s[right]; left--, right++) {
                if (right - left + 1 > bestLength) {
                    bestLeft = left;
                    bestLength = right - left + 1;
                }
            }
            for (int left = center, right = center + 1; left >= 0 && right < n && s[left] == s[right]; left--, right++) {
                if (right - left + 1 > bestLength) {
                    bestLeft = left;
                    bestLength = right - left + 1;
                }
            }
        }
        return s.substr(bestLeft, bestLength);
    }
};

Python

Python 3

class Solution:
    def longestPalindrome(self, s: str) -> str:
        best_left, best_length = 0, 0
        for center in range(len(s)):
            for left, right in ((center, center), (center, center + 1)):
                while left >= 0 and right < len(s) and s[left] == s[right]:
                    if right - left + 1 > best_length:
                        best_left, best_length = left, right - left + 1
                    left, right = left - 1, right + 1
        return s[best_left:best_left + best_length]

复杂度分析

共有 O(n) 个奇偶中心，每次扩展最多 O(n)，时间 O(n²)，额外空间 O(1)。

边界与易错点

空串返回空串；偶数长度回文必须以相邻双中心开始，不能只枚举单个字符中心。

模式迁移

需要“是否为回文”的许多区间查询时改用区间 DP；只求单个最长子串时中心扩展更直接。回到区间动态规划。