教程【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/gh_mirrors/in/InterviewGuide点击查看免费下载本文是 InterviewGuide「精选力扣 300 题目之动态规划」系列中关于「5. 最长回文子串」的完整题解原题笔记位于 docs/notes/03-hunting_job/03-algorithm/03-leetcode/11-动态规划/medium/5.最长回文子串.md。本篇文章在保留原笔记两版完整可运行代码的基础上逐行拆解「中心向外扩展」与「标准 DP」两种思路的推导过程与遍历顺序细节并结合仓库中 647. 回文子串、516. 最长回文子序列两道关联题帮你把「回文」这一高频面试考点一次性打通。一、题目描述与示例给定一个字符串s找到s中最长的回文子串。可以假设s的最大长度为 1000。示例 1输入: babad 输出: bab 注意: aba 也是一个有效答案。示例 2输入: cbbd 输出: bb题目的关键点有两个子串substring而非子序列subsequence子串必须是原字符串中连续的一段这一约束决定了 DP 状态转移与遍历顺序的设计回文palindrome正读反读相同如bab、abba。回文天然存在「中心对称」这一结构性质是后续两种解法共同的突破口。二、思路总览回文问题的两种经典范式在动手写代码前先建立对「回文子串」这类问题的整体认知。仓库中动态规划章节的导读 introduce.md 给出了字符匹配/区间类 DP 的通用方法论先假设状态dp[i][j]表示子串/子问题的状态再思考dp[i][j]与dp[i1][j]、dp[i][j-1]、dp[i1][j-1]之间的联系如果一时没有思路建议画表格辅助推导。针对本题存在两条经典路线解法核心思想时间复杂度空间复杂度中心向外扩展法枚举每个回文中心向左右两侧同步扩展O(n²)O(1)标准动态规划dp[i][j]记录区间[i, j]是否为回文利用区间递推O(n²)O(n²)Manacher 算法延伸利用对称性 回文半径数组加速O(n)O(n)原笔记收录了前两种解法的完整实现第三种 Manacher 算法作为延伸了解项放在文末面试中先掌握前两种即可覆盖绝大多数场景。三、方法一中心向外扩展法第一版自写实现3.1 算法原理回文串是关于中心对称的因此任何一个回文子串都可以从它的「中心」出发通过不断比较中心两侧的字符是否相等来生长奇数长度回文中心是单个字符如bab的中心是a偶数长度回文中心是两个相邻字符如abba的中心是bb。所以只需枚举字符串中每一个可能成为中心的位置共n个单字符中心 n-1个双字符中心合计约2n个对每个中心向左右扩展并记录下目前发现的最长回文即可。总复杂度为 O(n²)每个中心最坏扩展 O(n) 次。3.2 原版代码逐行讲解以下为原笔记第一版的完整代码一个核心思想是奇数中心与偶数中心共用同一个扩展函数Substrings。void Substrings(string s,string longestStr,int i,int j) { string left , right ; if (i j) { right s[j]; i--; } while ( i0 js.size() s[i]s[j]) { left s[i--]; rights[j]; } if (left.size() right.size() longestStr.size()) { reverse(left.begin(), left.end()); longestStr left right; } } string longestPalindrome(string s) { if (s.size() 1) return s; string longestStr ; for (int i 0; i s.size(); i) { Substrings(s, longestStr, i, i); Substrings(s, longestStr, i, i1); if (longestStr.size() s.size()) break;//自身就是个回文子串直接break就行 } return longestStr; }要点拆解Substrings(s, longestStr, i, i)处理奇数中心当i j时先把中心字符s[i]放入right随后指针i左移、j右移进入 while 循环向两侧扩展Substrings(s, longestStr, i, i1)处理偶数中心i、j从两个相邻位置出发跳过单个字符入队的逻辑直接比较s[i]与s[j]扩展条件i0 js.size() s[i]s[j]同时完成三件事——左边界不越界、右边界不越界、两侧字符相等一旦字符不等或触到边界立即停止拼接结果扩展得到的left是倒序收集的left s[i--]从中心向左逐个追加因此更新答案前先reverse(left.begin(), left.end())再以left right拼出完整回文串提前终止优化if (longestStr.size() s.size()) break;——一旦已经找到覆盖整个字符串的回文即整个s本身是回文无需继续枚举直接返回。原笔记记录的 LeetCode 提交表现为执行用时 124 ms内存消耗 46.8 MB均为当时 cpp 提交环境下的数据仅供参考不同语言与评测环境结果会有差异。3.3 一个常见的简化实现Substrings中用字符串累加再翻转来记录回文逻辑直观但存在多次字符串拼接开销。面试时更常见的写法是只记录最长回文的起止下标最后用substr一次性截取void expand(string s, int l, int r, int start, int maxLen) { while (l 0 r s.size() s[l] s[r]) { if (r - l 1 maxLen) { maxLen r - l 1; start l; } --l; r; } } string longestPalindrome(string s) { if (s.size() 1) return s; int start 0, maxLen 0; for (int i 0; i s.size(); i) { expand(s, i, i, start, maxLen); // 奇数中心 expand(s, i, i 1, start, maxLen); // 偶数中心 } return s.substr(start, maxLen); }该版本把「更新答案」收敛为仅记录start与maxLen空间开销进一步降到 O(1)逻辑也更贴近大多数题解的风格与原版思路完全等价。四、方法二标准动态规划解法4.1 状态定义与转移方程定义dp[i][j]表示子串s[i..j]闭区间是否为回文串是则为true。状态转移分情况讨论当s[i] s[j]时s[i..j]是否为回文取决于去掉首尾后的内部s[i1..j-1]是否为回文特判短区间当j - i 1即区间长度为 1 或 2时只要s[i] s[j]就一定是回文无需再查内部长度为 2 的aa内部为空区间长度为 1 的a自身必然回文。合并得到核心转移方程dp[i][j] (s[i] s[j]) (j - i 1 || dp[i 1][j - 1])这个方程的形态与 647. 回文子串中的 DP 完全一致详见下文关联题目小节是区间回文判断的通用模板。4.2 为什么i必须倒序遍历、j必须正序遍历这是本题 DP 最容易写错的地方。观察转移方程求解dp[i][j]需要依赖dp[i1][j-1]即「行号更大的上一行、列号更小的前一列」的格子。因此遍历顺序必须保证计算dp[i][j]时dp[i1][j-1]已经计算完毕。具体做法是外层循环i从n-1递减到0先算行号大的行这样i1行的结果必然早于i行得出内层循环j从i递增到n-1同行的j-1列先算同时保证j i只填充上三角矩阵避免无意义的下三角。画一张n x n的表格填一遍即 introduce.md 中建议的「画表格」法顺序就会非常直观每个格子的依赖都来自「左下角」的斜下方位置从下往上、从左往右填表即可。4.3 原版代码逐行讲解以下为原笔记第二版的完整代码string longestPalindrome(string s) { if (s.size() 1) return s; int n s.size(),low0,high0,longLen0; vectorvectorbool dp(n, vectorbool(n, false)); for (int i n-1; i 0; --i) { for (int j i; j n; j) { if (s[i] s[j] (j - i 1 || dp[i 1][j - 1])) { dp[i][j] true; if (j - i longLen) { longLen j - i; low i; high j; } } } } string longestStr ; while (low high) longestStr s[low]; return longestStr; }要点拆解二维布尔表初始化vectorvectorbool dp(n, vectorbool(n, false))全部初始化为false只有确认是回文的区间才置true转移条件与特判s[i] s[j] (j - i 1 || dp[i 1][j - 1])其中j - i 1正是对单字符与双字符区间的直接判定避免了访问dp[i1][j-1]时出现i1 j-1的无效区间答案追踪维护low、high记录当前最长回文的左右端点longLen记录长度仅当j - i longLen时更新保证「最长」语义结果还原while (low high) longestStr s[low];从low到high逐字符拼接出最终回文串。原笔记记录的 LeetCode 提交表现为执行用时 244 ms内存消耗 18.9 MB同为当时 cpp 提交环境数据。可以看出DP 版时间上比中心扩展法略慢每个区间都要完整遍历一遍n²个状态且布尔数组的随机访问模式相对朴素但思路更「机械化」、更易在面试中讲清楚推导过程。4.4 复杂度分析时间复杂度双重循环遍历全部n(n1)/2个区间O(n²)空间复杂度n x n布尔矩阵O(n²)vectorbool按位压缩存储实际占用远小于n²字节。针对题目给出的n 1000限制O(n²) 时间 O(n²) 空间完全在可接受范围内这也是该题被归为 Medium 难度、DP 解法可以作为标准答案的原因。五、两种方法对比与面试建议维度中心向外扩展法标准 DP思维难度依赖「回文中心对称」直觉易解释状态转移机械推导过程清晰时间复杂度O(n²)O(n²)空间复杂度O(1)O(n²)实现风险奇数/偶数中心易漏一个遍历顺序写错则答案错误适用扩展天然兼容「统计所有回文子串」兼容「统计回文子串」「求最长回文子序列」面试建议先口述中心扩展法的思路枚举 2n 个中心、左右扩展再给出 DP 的状态转移方程两种解法都要能在一分钟内说清DP 版务必当场画出「为什么i倒序」的依赖关系这是面试官最常追问的细节如果面试官追问 O(n) 解法可以提 Manacher 算法见下文但不要喧宾夺主把两种 O(n²) 解法讲扎实是第一要务。六、关联题目拓展把「回文」考点一次打通「最长回文子串」并非孤立题目InterviewGuide 动态规划章节还收录了另外两道回文题三者放在一起对比能更深刻理解「子串 / 子序列」对状态设计的影响。6.1 647. 回文子串统计数量原题笔记见 647.回文子串.md。题目要求统计字符串中所有回文子串的个数不同起止位置算不同子串如aaa共有 6 个三个单字符、两个aa、一个aaa。它与本题共享同一套 DP 转移方程if (s[i] s[j] (j - i 1 || dp[i 1][j - 1])) { dp[i][j] true; res; }区别仅在于本题遇到合法回文区间时累加计数而非记录最长区间。同时该笔记还收录了中心扩展法的计数版本——对每个中心向两侧扩展每扩展成功一次就计数一次奇数中心 偶数中心各跑一遍时间复杂度 O(n²)、空间 O(1)。可以说647 与 5 题是「同一套模板、两个问法」把 5 题的 DP 写好647 只需改动累加逻辑即可秒过。6.2 516. 最长回文子序列子串 → 子序列原题笔记见 516.最长回文子序列.md。注意区别子序列不要求连续如bbbab的最长回文子序列是bbbb长度 4而不是最长回文子串bbb。正因为不要求连续状态含义发生质变dp[i][j]表示s[i..j]区间内最长回文子序列的长度转移分为三种情况if (s[i] s[j] j - i 1) { dp[i][j] j - i 1; // 相邻或相同位置直接成回文 } else if (s[i] s[j]) { dp[i][j] dp[i 1][j - 1] 2; // 首尾相等长度 内部长度 2 } else { dp[i][j] max(dp[i 1][j], dp[i][j - 1]); // 首尾不等取删左或删右的较大者 }注意5 题的 DP 是布尔矩阵判断是否回文516 题的 DP 是整数矩阵记录最长长度且 516 在首尾不等时必须从dp[i1][j]与dp[i][j-1]中取最大值体现了「不连续」带来的自由度。两题放在一起对比记忆能明显提升对区间 DP 的掌控力。6.3 三道题的横向对比题目连续要求DP 状态含义核心转移5. 最长回文子串子串连续dp[i][j]是否为回文bools[i]s[j] (j-i1 || dp[i1][j-1])647. 回文子串子串连续同上累加res同上命中即res516. 最长回文子序列子序列可不连续dp[i][j]最长回文子序列长度int相等2不等取max(dp[i1][j], dp[i][j-1])三题的外层遍历顺序完全一致i从n-1递减、j从i递增因为都依赖左下角dp[i1][j-1]的结果——记住这一个遍历顺序规律三题通吃。七、延伸了解Manacher 算法O(n) 解法如果面试中希望展示更强的算法能力可以了解 Manacher马拉车算法。它通过在每个字符间隙插入分隔符把奇偶长度统一处理并利用已计算回文半径的对称性进行跳跃式扩展将时间复杂度优化到 O(n)。该算法在仓库当前题解笔记中未收录实现属于面试加分项而非必备项建议在把中心扩展法与 DP 讲透之后再自行补充学习此处不做展开。八、总结题目本质在 O(n²) 可接受的规模n 1000下求最长连续回文子串解法一中心扩展枚举 2n 个回文中心向两侧扩展O(n²) 时间、O(1) 空间实现最直观解法二标准 DPdp[i][j]布尔矩阵 区间递推关键是i倒序、j正序的遍历顺序O(n²) 时间、O(n²) 空间关联题647. 回文子串复用同一 DP 方程改为计数516. 最长回文子序列将布尔判断升级为长度记录体现子串与子序列的本质差异面试要点能口述两种思路、画出 DP 依赖关系、说清复杂度即可满分通过本考点。完整代码与更多题解见 5.最长回文子串.md同章节其他动态规划题目如 72.编辑距离、1143.最长公共子序列也遵循本小节总结的区间 DP 方法论可一并刷透。赞分享教程【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/gh_mirrors/in/InterviewGuide点击查看免费下载相关推荐LeetCode 5. 最长回文子串题解中心扩展法与动态规划附 Python / JavaScript / C 实现LeetCode 5. 最长回文子串题解中心扩展法与动态规划附 Python / JavaScript / C 实现 导读 本文基于 leetcode文档教程知识库NetEasyMusic下架歌曲自动切QQ音乐NetEasyMusic下架歌曲自动切QQ音乐 你在网易云搜那首歌提示无版权无法播放。用 NetEasyMusic 就不用手点换平台它会自动用歌名加教程codeforces-go 算法模板库LeetCode 5 最长回文子串题解中心扩展法 Manacher 算法codeforces go 算法模板库LeetCode 5 最长回文子串题解中心扩展法 Manacher 算法 导读 本文以 LeetCode 5.科学计算上一篇NCM解密工具ncmdump拖个文件把网易云音乐变成随处能放的MP3下一篇3dsconv 完整教程把 .3ds 卡带镜像快速变成 CIA 安装包创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考