5. 最长回文子串

难度：🟡 Medium | 标签：动归、中心扩展 | 状态：⬜ LeetCode 链接

思路

中心扩展最简洁：每个位置作中心（奇心 i / 偶心 i,i+1）向两边扩，记录最长。

DP 解：dp[i][j] = (s[i] == s[j]) && (j - i < 2 || dp[i+1][j-1])，二维 O(n²) 空间。 Manacher O(n) 进阶。

代码

class Solution {
    pair<int,int> expand(const string& s, int l, int r) {
        while (l >= 0 && r < (int)s.size() && s[l] == s[r]) { --l; ++r; }
        return {l + 1, r - 1};
    }
public:
    string longestPalindrome(string s) {
        int bestL = 0, bestR = 0;
        for (int i = 0; i < (int)s.size(); ++i) {
            auto [l1, r1] = expand(s, i, i);
            auto [l2, r2] = expand(s, i, i + 1);
            if (r1 - l1 > bestR - bestL) { bestL = l1; bestR = r1; }
            if (r2 - l2 > bestR - bestL) { bestL = l2; bestR = r2; }
        }
        return s.substr(bestL, bestR - bestL + 1);
    }
};

复杂度

• 时间 O(n²)，空间 O(1)
• Manacher O(n)，但代码繁

易错 / 回顾

• 奇心 / 偶心两套都要试
• 扩出循环后窗口是 [l+1, r-1]（左闭右闭）
• 不要忘记偶数中心 (i, i+1)