LeetCode 5 最长回文子串Longest Palindromic Substring完整解法指南从中心扩展到 Manacher 线性算法【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本指南围绕 hints/longest-palindromic-substring.md 的提示体系系统讲解 LeetCode 5「最长回文子串」的四种解法暴力枚举、动态规划、中心扩展Two Pointers与 Manacher 线性算法并逐一给出本仓库GitHub_Trending/leetcode1/leetcode中 Python、C、Go、Java、Rust、TypeScript 等多语言实现作为验证依据。读完本文你将掌握回文问题的核心分析框架能够针对不同数据规模选择时间复杂度从 O(n³) 到 O(n) 的合适方案。问题定义与推荐复杂度基线给定一个字符串s返回s中最长的回文子串。回文即正读反读相同的字符串例如babad的答案可以是bab或abacbbd的答案是bb。根据仓库提示文档的要求目标解法的复杂度应达到或优于 O(n²) 时间与 O(1) 空间其中n为给定字符串的长度。这个基线直接排除了下面将要介绍的暴力枚举法并指引我们优先掌握「中心扩展」思想——它正是提示文档 Hint 24 逐步引导的核心路径Hint 1暴力解法是检查每个子串是否为回文并返回最大长度整体 O(n³)应转向「以回文中心为思考单位」。Hint 2遍历字符串把当前字符当作中心同时向左右扩展仅在两侧字符相等时继续需同时考虑奇数长度与偶数长度两种情况。Hint 3维护resLen最长回文长度与res该回文的起始下标两个变量对每个下标从i - 1与i 1向外扩展可构造奇数长度回文。Hint 4偶数长度回文从下标i与i 1之间扩展用这种从中心出发的双指针技巧找出所有回文子串最后返回s[res : res resLen]。下文按复杂度递进依次展开四种解法核心代码可对照 articles/longest-palindromic-substring.md 的完整多语言版本。一、暴力枚举O(n³) 基线核心思路最朴素的想法是尝试每一个可能的子串s[i..j]用双指针l、r从两端向中间核对是否为回文若为回文且长度大于当前最优解则更新答案。该方案逻辑简单但存在大量重复比较——同一段子串会被反复校验。算法步骤初始化结果字符串与长度 0对每个起始下标i遍历结束下标j i用双指针检查s[i..j]是否为回文若是回文且更长则更新结果返回最长回文子串。复杂度时间复杂度O(n³)——枚举 O(n²) 个子串每次回文校验最坏 O(n)空间复杂度O(n)仅用于存储结果字符串。各语言实现以下 Python 实现完整对应提示文档 Hint 1 描述的暴力路径l、r双指针回文校验class Solution: def longestPalindrome(self, s: str) - str: res, resLen , 0 for i in range(len(s)): for j in range(i, len(s)): l, r i, j while l r and s[l] s[r]: l 1 r - 1 if l r and resLen (j - i 1): res s[i : j 1] resLen j - i 1 return resC 版本与上述逻辑一一对应只是用s.substr(i, j - i 1)提取子串Go 版本则通过s[i : j1]切片实现。该解法仅作为理解问题的起点实际提交会超时不推荐使用。二、动态规划O(n²) 时间、O(n²) 空间核心思路暴力法低效的根源在于反复校验相同子串。动态规划通过记忆化避免重复定义dp[i][j] true表示子串s[i..j]是回文。状态转移遵循两条规则首尾字符相等s[i] s[j]内部也是回文dp[i1][j-1]为真或区间长度不超过 3即j - i 2此时内部为空或单字符天然满足回文。由于dp[i][j]依赖左下角dp[i1][j-1]填充顺序必须从下到上i从n-1递减到 0j从i递增到n-1保证被依赖的格子已先计算。算法步骤令n len(s)创建n × n的布尔表dp初始化为false维护resIdx 0、resLen 0i从n-1到 0 递减j从i到n-1递增若s[i] s[j]且j - i 2或dp[i1][j-1]为真则标记dp[i][j] true并按需更新resIdx与resLen返回s[resIdx : resIdx resLen]。class Solution: def longestPalindrome(self, s: str) - str: resIdx, resLen 0, 0 n len(s) dp [[False] * n for _ in range(n)] for i in range(n - 1, -1, -1): for j in range(i, n): if s[i] s[j] and (j - i 2 or dp[i 1][j - 1]): dp[i][j] True if resLen (j - i 1): resIdx i resLen j - i 1 return s[resIdx : resIdx resLen]仓库中 java/0005-longest-palindromic-substring.java 的Solution3是同一思路的 Java 实现单字符对角线直接置真、相邻字符j - i 1时仅依赖字符相等、更长区间依赖isPalindrome[i1][j-1]并同步维护left与right边界。复杂度时间复杂度O(n²)双层循环各遍历一次空间复杂度O(n²)二维dp表。当n达到数千级别时O(n²) 空间可能成为瓶颈此时可考虑下面的中心扩展法。三、中心扩展Two PointersO(n²) 时间、O(1) 空间核心思路回文具有从中心对称展开的结构特点这是提示文档 Hint 24 的核心洞察。任意回文只有两种中心形态奇数长度中心是单个字符如racecar偶数长度中心位于两个字符之间如abba。因此无需枚举全部子串只需把每个位置当作潜在中心向外扩展l向左、r向右只要s[l] s[r]就继续扩大窗口并在过程中持续更新最长回文的起始下标与长度。相比 DP该方法既省去了二维表又避免了重复校验。算法步骤初始化resIdx 0、resLen 0对每个下标i奇数长度令l i、r i在l 0、r n且s[l] s[r]时向外扩展偶数长度令l i、r i 1同样条件下向外扩展每次扩展后若r - l 1超过resLen则更新两个结果变量返回s[resIdx : resIdx resLen]。class Solution: def longestPalindrome(self, s: str) - str: resIdx 0 resLen 0 for i in range(len(s)): # odd length l, r i, i while l 0 and r len(s) and s[l] s[r]: if (r - l 1) resLen: resIdx l resLen r - l 1 l - 1 r 1 # even length l, r i, i 1 while l 0 and r len(s) and s[l] s[r]: if (r - l 1) resLen: resIdx l resLen r - l 1 l - 1 r 1 return s[resIdx : resIdx resLen]仓库源码印证多种风格的中心扩展中心扩展是本仓库各语言实现的主流方案风格略有差异但核心一致Gogo/0005-longest-palindromic-substring.gol, r : i, i与l, r i, i1两轮循环用res直接保存子串、resLen保存长度Ccpp/0005-longest-palindromic-substring.cpp将扩展逻辑抽成私有方法middleOut(s, i, j, maxStart, maxLength)循环结束后通过j - i - 1计算回文长度、i 1定位起始下标注意其maxLength初始化为 1 以正确处理单字符输入Javajava/0005-longest-palindromic-substring.javaSolution1是标准版本Solution2额外做了「连续相同字符压缩」优化——先让i跳过连续相等字符s.charAt(i) s.charAt(i 1)时i再向两侧扩展Rustrust/0005-longest-palindromic-substring.rs使用Vecchar便于按字符索引且对length 1单独提前返回TypeScripttypescript/0005-longest-palindromic-substring.ts与 Python 版本结构几乎一致通过s.slice(l, r 1)截取。复杂度时间复杂度O(n²)——每个中心扩展最坏 O(n)共 2n 个中心含偶数中心空间复杂度O(1) 额外空间O(n) 用于存放输出字符串。此方案正好满足提示文档设定的O(n²) 时间 O(1) 空间推荐基线是面试中的标准答案。四、Manacher 算法O(n) 线性时间核心思路中心扩展虽然空间最优但对每个中心都要独立向外扩展存在大量重复比较。Manacher 算法的关键创新在于利用已知回文的对称性复用结果统一奇偶在字符之间及两端插入特殊分隔符#例如abba→#a#b#b#a#使所有回文都变成以某个字符为中心的奇数长度回文镜像复用维护当前最右回文的中心center与右边界right当新位置i落在该回文内部时先用其关于center的镜像位置l (r - i)的半径初始化p[i]再继续向外扩展动态推进若扩展后的回文越过right则更新center与right。数组p[i]记录变换后字符串中以i为中心的回文半径。处理完毕后取p的最大值对应的下标center_idx与半径resLen通过(center_idx - resLen) // 2还原到原字符串的起始下标。class Solution: def longestPalindrome(self, s: str) - str: def manacher(s): t # #.join(s) # n len(t) p [0] * n l, r 0, 0 for i in range(n): p[i] min(r - i, p[l (r - i)]) if i r else 0 while (i p[i] 1 n and i - p[i] - 1 0 and t[i p[i] 1] t[i - p[i] - 1]): p[i] 1 if i p[i] r: l, r i - p[i], i p[i] return p p manacher(s) resLen, center_idx max((v, i) for i, v in enumerate(p)) resIdx (center_idx - resLen) // 2 return s[resIdx : resIdx resLen]算法步骤变换字符串在字符间及两端插入#创建半径数组pp[i]表示变换后以i为中心的回文半径维护center与right两个指针对每个i若在已知回文内部则用镜像初始化p[i]再对称扩展若超出right则更新center与right找出p的最大值反推原串下标返回最长回文子串。复杂度时间复杂度O(n)——每个字符最多被扩展一次镜像初始化保证总工作量线性空间复杂度O(n)存储半径数组与变换后的字符串。需要注意Manacher 实现中的边界条件i p[i] 1 n、i - p[i] - 1 0极易出错建议对照 articles/longest-palindromic-substring.md 中 Java/C/Go/Rust 等版本逐行核对。该算法属于进阶内容面试中通常作为加分项实际工程中可用性极高。五、常见陷阱与边界情况1. 必须同时处理奇偶两种中心中心扩展时若只从(i, i)扩展会漏掉abba这类偶数长度回文若只从(i, i1)扩展会漏掉aba。每个位置都要同时尝试两种中心这正是提示文档 Hint 2 强调的核心。2. 子串提取的越界与偏移扩展循环退出时l与r通常已经越过回文边界各一步。若采用先扩展后计算的写法如 C 版middleOut需用i 1与j - i - 1修正若采用扩展过程中实时记录的写法如 Python 版则直接以s[l:r1]截取。务必用a、aa等最小用例验证下标。3. 单字符字符串的结果初始化输入a时最长回文子串就是a本身。若结果初始化为空串、且仅在发现更长回文时才更新则可能对单字符输入返回空串。正确的做法是将resLen初始化为 0、resIdx初始化为 0保证至少返回s[0]或如 cpp/0005-longest-palindromic-substring.cpp 与 rust/0005-longest-palindromic-substring.rs 那样将maxLength初始化为 1或对length 1提前返回。4. 空串与全同字符输入空串应直接返回空串resLen为 0 时循环不执行全同字符如aaaa则是偶数/奇数中心扩展的极限压力测试可用于验证算法不会遗漏最长窗口。六、解法对比与选型建议解法时间复杂度空间复杂度适用场景暴力枚举O(n³)O(n)仅用于理解问题实际不可用动态规划O(n²)O(n²)适合需要同时查询大量子串回文性的场景可复用dp表中心扩展O(n²)O(1)面试标准答案满足提示文档推荐基线ManacherO(n)O(n)超长字符串或追求最优解时使用从提示文档的递进式 Hint 可以看出推荐的学习路径是先能写出 O(n³) 暴力解再理解 DP 的状态转移最后掌握中心扩展的奇偶双中心技巧——它同时满足 O(n²) 时间与 O(1) 空间的推荐基线。Manacher 作为进阶补充为需要线性解法的场景提供最终方案。本仓库在 c、csharp、javascript、kotlin、swift 等目录下还提供了更多语言的同题实现可作为交叉验证与多语言语法对照的参考资料。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考