LeetCode 5. 最长回文子串题解中心扩展法与动态规划附 Python / JavaScript / C 实现【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读本文基于 leetcode 题解仓库中的 5. 最长回文子串 题解展开系统讲解求解字符串最大回文子串的两种经典方法中心扩展与区间动态规划。全文完整继承原题解的题目分析、核心思想与三种语言Python / JavaScript / C的参考实现并结合仓库源码对状态转移、base case、遍历顺序与复杂度进行逐层拆解。读完本文你将掌握回文延伸这一解决回文类问题的通用模型并能够独立推导与实现最长回文子串的 O(N²) 解法为后续理解马拉车算法Manacher与最长回文子序列等进阶题目打下基础。题目描述与示例给定一个字符串s找到s中最长的回文子串。可以假设s的最大长度为 1000。示例 1输入: babad 输出: bab 注意: aba 也是一个有效答案。示例 2输入: cbbd 输出: bb回文串Palindrome的定义是正读与反读相同的字符串例如level、noon。判断单个字符串是否为回文通常使用首尾双指针而求最长回文子串这类最优化问题则需要利用回文的递归结构参见仓库中 字符串问题专题 对回文类问题的归类。前置知识回文Palindrome的基本概念与判定方法动态规划Dynamic Programming基础状态定义、状态转移、边界条件双指针 / 中心扩展思想。本题在仓库题解中属于高频面试题常出现于阿里、百度、腾讯等公司面试考察中。核心思路延伸extend解决回文最优化问题的核心思想可以用两个字概括——延伸。具体来说回文串存在如下两个重要的结构性质如果一个字符串是回文串那么在它左右两侧分别加上一个相同的字符得到的字符串一定仍是回文串反过来如果在一个不是回文字符串的字符串两端添加任何字符或者在回文串左右分别添加不同的字符得到的一定不是回文串。这两条性质给出了回文串从小到大生长的规律任何长度大于 2 的回文串都可以看作在某个更短的回文串两侧包上两个相同字符得到任何非回文串无论怎么包裹都无法变成回文串。基于此我们有了最小单元base case单字符任意单个字符本身就是回文其对称轴是字符本身双字符两个相同字符构成回文其对称轴是介于两者之间的虚拟点两个不同字符则不构成回文。回文这个性质天然地在大问题长回文串与小问题短回文串之间建立了关联因此既可以通过中心向两侧延伸直接枚举也可以将其翻译成区间动态规划的转移方程。方法一中心扩展法推荐直觉实现中心扩展法正是上述延伸思想的直接落地枚举字符串中的每一个位置作为回文中心从中心向左右两侧同步扩展只要左右字符相等就继续延伸当两侧字符不等或越界时停止此时得到以该中心为轴的最长回文串由于对称轴有两种形态单字符本身、双字符间隙每个位置需要尝试两种扩展起点(i, i)与(i, i 1)。复杂度分析共有 O(N) 个中心约 2N 个扩展起点每个中心最多向外扩展 O(N) 次因此时间复杂度为 O(N²)仅使用常数级额外空间空间复杂度为 O(1)。方法二区间动态规划同样基于延伸规律可以用二维数组dp[i][j]表示字符串s中从下标i到j包含两端的子串是否为回文。状态转移方程只是将延伸规律转化为代码if (s[i] s[j] dp[i 1][j - 1]) { dp[i][j] true; }即只有当两端字符相等且去掉两端后的内部子串s[i1..j-1]已经是回文时s[i..j]才是回文。边界条件base casej - i 0单字符子串dp[i][j] truej - i 1 s[i] s[j]双字符且相同dp[i][j] true。遍历顺序的讲究由于dp[i][j]依赖dp[i 1][j - 1]即行号更大的状态因此在 JavaScript 实现中采用从下往上i从n-1到0、从左往右j从i到n-1的遍历保证计算dp[i][j]时dp[i1][j-1]已经求出。每得到一个dp[i][j] true的状态就用j - i 1与当前答案长度比较并更新结果子串。复杂度分析状态总数为 O(N²)每个状态的转移为 O(1)时间复杂度 O(N²)二维数组存储全部状态空间复杂度 O(N²)。参考代码完整继承原题解原题解代码支持Python、JavaScript、C三种语言其中 Python 与 C 版本采用中心扩展法JavaScript 版本采用动态规划法两者互为印证。Python Code中心扩展class Solution: def longestPalindrome(self, s: str) - str: n len(s) if n 0: return res s[0] def extend(i, j, s): while(i 0 and j len(s) and s[i] s[j]): i - 1 j 1 return s[i 1:j] for i in range(n - 1): e1 extend(i, i, s) e2 extend(i, i 1, s) if max(len(e1), len(e2)) len(res): res e1 if len(e1) len(e2) else e2 return res实现要点extend(i, j, s)从中心(i, j)向外扩展循环退出时s[i] ! s[j]或越界此时真正有效的回文区间是s[i1 : j]左闭右开切片正好取到j-1写法十分精妙。JavaScript Code动态规划/* * lc appleetcode id5 langjavascript * * [5] Longest Palindromic Substring */ /** * param {string} s * return {string} */ var longestPalindrome function (s) { // babad // tag : dp if (!s || s.length 0) return ; let res s[0]; const dp []; // 倒着遍历简化操作 这么做的原因是dp[i][..]依赖于dp[i 1][..] for (let i s.length - 1; i 0; i--) { dp[i] []; for (let j i; j s.length; j) { if (j - i 0) dp[i][j] true; // specail case 1 else if (j - i 1 s[i] s[j]) dp[i][j] true; // specail case 2 else if (s[i] s[j] dp[i 1][j - 1]) { // state transition dp[i][j] true; } if (dp[i][j] j - i 1 res.length) { // update res res s.slice(i, j 1); } } } return res; };实现要点注释中明确指出了倒着遍历的原因——dp[i][..]依赖dp[i 1][..]两个special case分别对应单字符与双字符的 base cases.slice(i, j 1)取当前最优回文子串。CPP Code中心扩展class Solution { private: int expand(string s, int L, int R) { while (L 0 R s.size() s[L] s[R]) { --L; R; } return R - L - 1; } public: string longestPalindrome(string s) { if (s.empty()) return s; int start 0, maxLen 0; for (int i 0; i s.size(); i) { int len1 expand(s, i, i); int len2 expand(s, i, i 1); int len max(len1, len2); if (len maxLen) { start i - (len - 1) / 2; maxLen len; } } return s.substr(start, maxLen); } };实现要点expand返回扩展得到的回文长度R - L - 1因为退出循环时 L、R 各多走了一步分别以(i, i)和(i, i 1)为轴扩展并取较大者通过start i - (len - 1) / 2反推出回文起点最后用substr(start, maxLen)截取结果。复杂度分析统一结论时间复杂度$O(N^2)$ —— 中心扩展需要枚举全部 O(N) 个中心并各扩展 O(N)动态规划需要枚举 O(N²) 个状态。空间复杂度中心扩展法为 $O(1)$动态规划法为 $O(N^2)$二维 DP 表。相关题目最长回文子序列516回文延伸模型并不局限于子串也适用于子序列问题。仓库中的 516. 最长回文子序列 是本题最直接的姊妹题二者的区别在于子串要求连续s[i] s[j]且内部s[i1..j-1]为回文时dp[i][j] true子序列不要求连续当s[i] s[j]时回文长度2否则取max(dp[i1][j], dp[i][j-1])。516 题的状态转移为if (s[i] s[j]) { dp[i][j] dp[i 1][j - 1] 2; } else { dp[i][j] Math.max(dp[i][j - 1], dp[i 1][j]); }两题共享从中心/内部向外延伸、两端同字符决定能否扩展的核心思想建议对照阅读以加深对回文类动态规划的理解。此外仓库 字符串问题专题 还将回文相关的 125. 验证回文串、131. 分割回文串 等题目归入同一知识簇并指出当需要进一步把时间优化到 O(N) 时可学习利用回文对称性的马拉车算法Manacher。小结本文围绕最长回文子串这一经典问题完整继承了仓库原题解的核心内容并扩展了实现细节核心思想是延伸回文只能由更短的回文两侧加相同字符得到非回文串无法通过两端扩展变成回文两种解法中心扩展直觉、O(N²) 时间、O(1) 空间与区间动态规划dp[i][j]判断子串是否回文、O(N²) 时间、O(N²) 空间仓库题解分别用 Python/CPP 与 JavaScript 给出实现可对照学习知识迁移同一延伸模型可推广到最长回文子序列等回文类问题并通向马拉车算法等进阶优化。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 5. 最长回文子串题解：中心扩展法与动态规划（附 Python / JavaScript / C++ 实现）
LeetCode 5. 最长回文子串题解中心扩展法与动态规划附 Python / JavaScript / C 实现【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读本文基于 leetcode 题解仓库中的 5. 最长回文子串 题解展开系统讲解求解字符串最大回文子串的两种经典方法中心扩展与区间动态规划。全文完整继承原题解的题目分析、核心思想与三种语言Python / JavaScript / C的参考实现并结合仓库源码对状态转移、base case、遍历顺序与复杂度进行逐层拆解。读完本文你将掌握回文延伸这一解决回文类问题的通用模型并能够独立推导与实现最长回文子串的 O(N²) 解法为后续理解马拉车算法Manacher与最长回文子序列等进阶题目打下基础。题目描述与示例给定一个字符串s找到s中最长的回文子串。可以假设s的最大长度为 1000。示例 1输入: babad 输出: bab 注意: aba 也是一个有效答案。示例 2输入: cbbd 输出: bb回文串Palindrome的定义是正读与反读相同的字符串例如level、noon。判断单个字符串是否为回文通常使用首尾双指针而求最长回文子串这类最优化问题则需要利用回文的递归结构参见仓库中 字符串问题专题 对回文类问题的归类。前置知识回文Palindrome的基本概念与判定方法动态规划Dynamic Programming基础状态定义、状态转移、边界条件双指针 / 中心扩展思想。本题在仓库题解中属于高频面试题常出现于阿里、百度、腾讯等公司面试考察中。核心思路延伸extend解决回文最优化问题的核心思想可以用两个字概括——延伸。具体来说回文串存在如下两个重要的结构性质如果一个字符串是回文串那么在它左右两侧分别加上一个相同的字符得到的字符串一定仍是回文串反过来如果在一个不是回文字符串的字符串两端添加任何字符或者在回文串左右分别添加不同的字符得到的一定不是回文串。这两条性质给出了回文串从小到大生长的规律任何长度大于 2 的回文串都可以看作在某个更短的回文串两侧包上两个相同字符得到任何非回文串无论怎么包裹都无法变成回文串。基于此我们有了最小单元base case单字符任意单个字符本身就是回文其对称轴是字符本身双字符两个相同字符构成回文其对称轴是介于两者之间的虚拟点两个不同字符则不构成回文。回文这个性质天然地在大问题长回文串与小问题短回文串之间建立了关联因此既可以通过中心向两侧延伸直接枚举也可以将其翻译成区间动态规划的转移方程。方法一中心扩展法推荐直觉实现中心扩展法正是上述延伸思想的直接落地枚举字符串中的每一个位置作为回文中心从中心向左右两侧同步扩展只要左右字符相等就继续延伸当两侧字符不等或越界时停止此时得到以该中心为轴的最长回文串由于对称轴有两种形态单字符本身、双字符间隙每个位置需要尝试两种扩展起点(i, i)与(i, i 1)。复杂度分析共有 O(N) 个中心约 2N 个扩展起点每个中心最多向外扩展 O(N) 次因此时间复杂度为 O(N²)仅使用常数级额外空间空间复杂度为 O(1)。方法二区间动态规划同样基于延伸规律可以用二维数组dp[i][j]表示字符串s中从下标i到j包含两端的子串是否为回文。状态转移方程只是将延伸规律转化为代码if (s[i] s[j] dp[i 1][j - 1]) { dp[i][j] true; }即只有当两端字符相等且去掉两端后的内部子串s[i1..j-1]已经是回文时s[i..j]才是回文。边界条件base casej - i 0单字符子串dp[i][j] truej - i 1 s[i] s[j]双字符且相同dp[i][j] true。遍历顺序的讲究由于dp[i][j]依赖dp[i 1][j - 1]即行号更大的状态因此在 JavaScript 实现中采用从下往上i从n-1到0、从左往右j从i到n-1的遍历保证计算dp[i][j]时dp[i1][j-1]已经求出。每得到一个dp[i][j] true的状态就用j - i 1与当前答案长度比较并更新结果子串。复杂度分析状态总数为 O(N²)每个状态的转移为 O(1)时间复杂度 O(N²)二维数组存储全部状态空间复杂度 O(N²)。参考代码完整继承原题解原题解代码支持Python、JavaScript、C三种语言其中 Python 与 C 版本采用中心扩展法JavaScript 版本采用动态规划法两者互为印证。Python Code中心扩展class Solution: def longestPalindrome(self, s: str) - str: n len(s) if n 0: return res s[0] def extend(i, j, s): while(i 0 and j len(s) and s[i] s[j]): i - 1 j 1 return s[i 1:j] for i in range(n - 1): e1 extend(i, i, s) e2 extend(i, i 1, s) if max(len(e1), len(e2)) len(res): res e1 if len(e1) len(e2) else e2 return res实现要点extend(i, j, s)从中心(i, j)向外扩展循环退出时s[i] ! s[j]或越界此时真正有效的回文区间是s[i1 : j]左闭右开切片正好取到j-1写法十分精妙。JavaScript Code动态规划/* * lc appleetcode id5 langjavascript * * [5] Longest Palindromic Substring */ /** * param {string} s * return {string} */ var longestPalindrome function (s) { // babad // tag : dp if (!s || s.length 0) return ; let res s[0]; const dp []; // 倒着遍历简化操作 这么做的原因是dp[i][..]依赖于dp[i 1][..] for (let i s.length - 1; i 0; i--) { dp[i] []; for (let j i; j s.length; j) { if (j - i 0) dp[i][j] true; // specail case 1 else if (j - i 1 s[i] s[j]) dp[i][j] true; // specail case 2 else if (s[i] s[j] dp[i 1][j - 1]) { // state transition dp[i][j] true; } if (dp[i][j] j - i 1 res.length) { // update res res s.slice(i, j 1); } } } return res; };实现要点注释中明确指出了倒着遍历的原因——dp[i][..]依赖dp[i 1][..]两个special case分别对应单字符与双字符的 base cases.slice(i, j 1)取当前最优回文子串。CPP Code中心扩展class Solution { private: int expand(string s, int L, int R) { while (L 0 R s.size() s[L] s[R]) { --L; R; } return R - L - 1; } public: string longestPalindrome(string s) { if (s.empty()) return s; int start 0, maxLen 0; for (int i 0; i s.size(); i) { int len1 expand(s, i, i); int len2 expand(s, i, i 1); int len max(len1, len2); if (len maxLen) { start i - (len - 1) / 2; maxLen len; } } return s.substr(start, maxLen); } };实现要点expand返回扩展得到的回文长度R - L - 1因为退出循环时 L、R 各多走了一步分别以(i, i)和(i, i 1)为轴扩展并取较大者通过start i - (len - 1) / 2反推出回文起点最后用substr(start, maxLen)截取结果。复杂度分析统一结论时间复杂度$O(N^2)$ —— 中心扩展需要枚举全部 O(N) 个中心并各扩展 O(N)动态规划需要枚举 O(N²) 个状态。空间复杂度中心扩展法为 $O(1)$动态规划法为 $O(N^2)$二维 DP 表。相关题目最长回文子序列516回文延伸模型并不局限于子串也适用于子序列问题。仓库中的 516. 最长回文子序列 是本题最直接的姊妹题二者的区别在于子串要求连续s[i] s[j]且内部s[i1..j-1]为回文时dp[i][j] true子序列不要求连续当s[i] s[j]时回文长度2否则取max(dp[i1][j], dp[i][j-1])。516 题的状态转移为if (s[i] s[j]) { dp[i][j] dp[i 1][j - 1] 2; } else { dp[i][j] Math.max(dp[i][j - 1], dp[i 1][j]); }两题共享从中心/内部向外延伸、两端同字符决定能否扩展的核心思想建议对照阅读以加深对回文类动态规划的理解。此外仓库 字符串问题专题 还将回文相关的 125. 验证回文串、131. 分割回文串 等题目归入同一知识簇并指出当需要进一步把时间优化到 O(N) 时可学习利用回文对称性的马拉车算法Manacher。小结本文围绕最长回文子串这一经典问题完整继承了仓库原题解的核心内容并扩展了实现细节核心思想是延伸回文只能由更短的回文两侧加相同字符得到非回文串无法通过两端扩展变成回文两种解法中心扩展直觉、O(N²) 时间、O(1) 空间与区间动态规划dp[i][j]判断子串是否回文、O(N²) 时间、O(N²) 空间仓库题解分别用 Python/CPP 与 JavaScript 给出实现可对照学习知识迁移同一延伸模型可推广到最长回文子序列等回文类问题并通向马拉车算法等进阶优化。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考