题目描述

题目链接：力扣 5. 最长回文子串

题目描述：

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

示例 2：
输入：s = “cbbd”
输出：“bb”

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

为什么这道题值得花上几分钟弄明白？

这道题是字符串题型的经典重难点，更是面试中“区分基础与进阶”的核心考察题——它不仅要求你掌握字符串遍历、子串判断等基础操作，更需要理解“中心扩展”“动态规划”等核心算法思想，是夯实算法思维、提升代码优化能力的绝佳案例。

题目核心价值

• 算法思想的“练兵场”：同一问题可通过“暴力枚举”“中心扩展”“动态规划”等多种思路解决，能让我们深刻体会不同算法的设计逻辑、时间/空间复杂度差异，培养“一题多解”的思维习惯。
• 动态规划的“入门典范”：本题的动态规划解法逻辑清晰、状态转移直观，是理解“区间 DP”（状态表示为区间 [i,j]）的最佳入门案例，后续遇到“最长回文子序列”“最长公共子序列”等问题时可直接迁移思路。
• 边界处理的“试金石”：单字符字符串、双字符字符串、全相同字符字符串、无长度≥2回文子串等特殊场景，能充分检验代码的稳健性，避免“看似能过样例，实则漏洞百出”。
• 工程化思维的“缩影”：回文子串查找在实际工作中高频出现（如文本编辑中的回文检测、生物信息学中的基因序列分析、密码学中的对称字符串处理），解题思路可直接复用。
• 面试的“分水岭”：作为字符串题型的进阶题，常出现在笔试中档题或面试核心环节，能快速写出“中心扩展”或“动态规划”解法，是证明自己算法基础扎实、思维灵活的重要依据。

面试考察的核心方向

1. 算法思路的多样性：能否想出至少两种解法（如中心扩展+动态规划），并分析各自的优劣。
2. 逻辑拆解能力：能否将“找最长回文子串”的问题，拆分为“判断子串是否为回文”“枚举所有可能回文子串”“优化枚举效率”等子问题。
3. 边界条件的考虑：是否能覆盖单字符、双字符、全相同字符等特殊用例，体现代码的鲁棒性。
4. 时间/空间复杂度优化：能否从暴力枚举的 O(n³) 优化到 O(n²)（中心扩展/动态规划），体现优化意识。

算法原理

中心扩展方法（双指针）

核心思路：
回文子串的本质是“对称”——奇数长度的回文子串以“单个字符”为中心对称（如“bab”以中间的“a”为中心），偶数长度的回文子串以“两个相邻字符”为中心对称（如“bb”以两个“b”之间的间隙为中心）。

所以，我们可以：

1. 枚举所有可能的“中心”（单个字符或两个相邻字符）；
2. 对每个中心，用双指针向左右扩展，直到左右指针指向的字符不同或越界；
3. 记录扩展过程中找到的最长回文子串的长度和起始位置。

细节分析：
我们选定一个点为这个子串的中心，用两个指针向左右扩展，会出现两种情况：
1.最长子串是奇数：两个指针都从我们选定的点开始即可，判断两个指针所指的字符串是否相同，最后记录长度。
2.最长子串是偶数：这时我们就要让两个指针分别指向两个相邻的点才能不漏情况，从选定的点左或右都可以，同样之后向两边扩展。

动态规划

核心思路：
利用动态规划的“空间换时间”思想，将“判断区间 [i,j] 是否为回文子串”的结果存储在二维数组 dp[i][j] 中，避免重复判断。

1.明确状态表示含义
dp[i][j]:表示 字符串s 中 [i,j]（以i开头到j结尾的）区间是否为回文串。

2.动态转移方程
我们分析i j的时候会有两种情况：
1.s[i] != s[j]:那么dp[i][j] = flase
2.s[i] = s[j]:
那么此时又可以分为三种情况
（1）i = j ：那么就可以确定dp[i][j] = ture
（2）j = i+1 : 同样也可以确定dp[i][j] = ture
（3）i+1 < j：这是我们要根据dp[i+1][j-1]来确定，如果dp[i+1][j-1]是回文串那么dp[i][j]也是，否则不是

3.初始化
当 j < i 的时候是没有意义的，而我们动态转移方程中又包含 j == i 与 j == i + 1 这两种情况所以我们不用初始化。

4.填表顺序
从下向上填表，横向都可以。

5.返回值
我们要返回的是最长的回文子串，并且在dp表中我们可以明确的知道[i,j]是否是回文串，那么我们只需要找到最长的回文串和起点i，返回从i截取最长长度的字符串即可。

代码实现

中心扩展法（双指针）

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

class Solution {
public:
    string longestPalindrome(string s) {
        // 边界处理：字符串长度≤1，直接返回原字符串
        if (s.size() <= 1) return s;
        int start = 0;  // 最长回文子串的起始索引
        int maxLen = 1; // 最长回文子串的长度（初始为1，至少有一个字符）

        // 遍历每个可能的中心，分别处理奇数和偶数长度的回文
        for (int i = 0; i < s.size(); i++) {
            // 情况1：奇数长度回文（以单个字符s[i]为中心）
            expand(s, i, i, start, maxLen);
            // 情况2：偶数长度回文（以s[i]和s[i+1]为中心）
            expand(s, i, i + 1, start, maxLen);
        }

        // 截取最长回文子串（从start开始，长度为maxLen）
        return s.substr(start, maxLen);
    }

    // 辅助函数：从中心(left, right)向左右扩展，更新最长回文子串的start和maxLen
    void expand(string& s, int left, int right, int& start, int& maxLen) {
        // 满足边界条件且左右字符相等，继续扩展
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            left--;
            right++;
        }
        // 扩展停止后，当前回文子串的实际长度为 (right - 1) - (left + 1) + 1 = right - left - 1
        int currentLen = right - left - 1;
        // 若当前长度大于最大长度，更新start和maxLen
        if (currentLen > maxLen) {
            maxLen = currentLen;
            start = left + 1;  // 因为最后一次left--导致左边界多减了1，需加1恢复
        }
    }
};

代码细节与易错点

• 边界处理：必须先判断字符串长度≤1的情况，避免后续扩展逻辑无效。

• 长度计算：扩展停止后，left 和 right 已越界或字符不同，实际回文子串的边界是 left+1 到 right-1，长度为 right - left - 1（易错点：直接用 right - left + 1 会导致长度计算错误，要注意left和right并不包括在我们目标字符串中，如下图👇）。
  

• 指针越界：扩展时需同时判断 left >= 0 和 right < s.size()，避免数组越界访问。

复杂度分析

• 时间复杂度：O(n²)。字符串长度为 n，共有 2n-1 个中心（n 个奇数中心 + n-1 个偶数中心），每个中心的扩展最多遍历 n 个字符，总复杂度为 O(n×2n) = O(n²)。
• 空间复杂度：O(1)。仅使用常数个变量存储起始位置、长度等信息，无额外空间开销。

动态规划（区间 DP）

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

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        // 边界处理：字符串长度≤1，直接返回原字符串
        if (n <= 1) return s;

        // dp[i][j]：表示s[i..j]是否为回文子串
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        int start = 0;  // 最长回文子串的起始索引
        int maxLen = 1; // 最长回文子串的长度（初始为1）

        // 填表顺序：从下到上（i从n-1到0），从左到右（j从i到n-1）
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                // 状态转移方程：s[i] == s[j]时，根据区间长度判断是否为回文
                if (s[i] == s[j]) {
                    dp[i][j] = (j - i <= 1) ? true : dp[i + 1][j - 1];
                } else {
                    dp[i][j] = false;
                }

                // 若当前区间是回文子串，且长度大于maxLen，更新记录
                if (dp[i][j] && (j - i + 1 > maxLen)) {
                    maxLen = j - i + 1;
                    start = i;
                }
            }
        }

        // 截取并返回最长回文子串
        return s.substr(start, maxLen);
    }
};

代码细节与易错点

• 填表顺序：必须“从下到上、从左到右”，因为 dp[i][j] 依赖 dp[i+1][j-1]（i+1 比 i 大，所以 i 要从大到小遍历）。
• 区间长度判断：j - i <= 1 是关键条件，覆盖了“单个字符”和“两个相同字符”的情况，避免遗漏。
• 初始化：dp 数组无需提前赋值，因为转移方程已覆盖所有 i <= j 的情况。

复杂度分析

• 时间复杂度：O(n²)。需遍历 n×n 个区间（i 从 0 到 n-1，j 从 i 到 n-1），每个区间的判断仅需 O(1) 时间；
• 空间复杂度：O(n²)。使用了 n×n 大小的二维数组 dp 存储状态。

总结

核心考点回顾

1. 算法思想的理解：中心扩展法的“对称特性”、动态规划的“区间状态表示”，体现了“问题转化”和“空间换时间”的核心思想；
2. 逻辑拆解能力：将“找最长回文子串”拆分为“枚举中心/区间”“验证回文”“记录最长子串”三个步骤，避免逻辑混乱；
3. 边界处理：覆盖字符串长度≤1、双字符相同/不同、全相同字符等特殊场景，是代码鲁棒性的关键；
4. 代码优化意识：从暴力枚举的 O(n³) 优化到 O(n²)，体现了“减少重复计算”的优化思路；

解题思路迁移

• 区间 DP 迁移：本题的动态规划解法可直接迁移到“最长回文子序列”“最长公共子序列”“回文子串个数”等问题，核心是“状态表示为区间 [i,j]”；
• 中心对称思想迁移：在“回文数判断”“对称字符串匹配”等问题中，可复用“双指针向中心/两侧扩展”的逻辑；
• 辅助函数解耦：将重复逻辑（如中心扩展）抽离为独立函数，是工程化开发中提升代码可读性和复用性的常用技巧。

常见错误总结

1. 中心扩展法中长度计算错误：误将 right - left + 1 作为回文子串长度，忽略扩展后指针已越界的情况；
2. 动态规划填表顺序错误：从上到下遍历 i，导致 dp[i+1][j-1] 未被计算，逻辑出错；
3. 忽略边界条件：未处理字符串长度≤1的情况，导致后续逻辑无效；
4. 动态规划中遗漏 j - i <= 1 的判断：导致长度为2的相同字符子串（如“bb”）被误判为非回文。

下题预告

下一篇我们将攻克字符串与数学结合的经典基础题——力扣 67. 二进制求和！这道题虽然简单但是在不投机取巧的情况下其中细节点很多，需要掌握字符串的遍历、字符转换等基础操作，是夯实“字符串模拟数学运算”思路的绝佳案例。

Doro 带着小花🌸来啦！🌸奖励🌸坚持攻克重难点的你！复杂问题拆解后也能轻松应对，下一道题虽然是基础题，但细节决定成败，跟着思路一步步梳理，一定能写出简洁高效的代码～ 如果这篇本文章对你有帮助别忘了点赞，收藏哦~，关注这个博主后续刷题时直接找到他随时回顾知识点，也欢迎在评论区分享你的解题感悟，我们下道题不见不散！