LeetCode 5. 最长回文子串——中心扩展法彻底讲透

首页/资讯中心/详情
发布时间：2026/6/30 13:00:29
LeetCode 5. 最长回文子串——中心扩展法彻底讲透
LeetCode 5. 最长回文子串——中心扩展法彻底讲透一、题目描述给定一个字符串s找到其中最长的回文子串并返回这个子串。示例输入s babad 输出bab 解释aba 同样是符合题意的答案。输入s cbbd 输出bb二、什么是回文串回文串Palindrome正着读和反着读完全一样的字符串。例如a aa aba abba racecar都属于回文串。而ab abc abca不是回文串。三、回文的核心性质左右对称所有回文串一定存在一个「对称中心」。例如奇数长度回文aba a ← b → a中心是b偶数长度回文abba ab ← → ba中心是两个字符之间的缝隙因此只要找到所有可能的对称中心然后不断向两边扩散就能找到所有回文串。这就是中心扩展法。四、整体思路对于字符串中的每一个位置i我们都尝试两种情况情况1奇数回文expand(i,i)例如aba ^情况2偶数回文expand(i,i1)例如abba ^^每次扩散结束后记录当前回文的长度。如果比之前最长的回文还长就更新答案。五、扩散函数怎么写定义函数expand(left,right)表示从left和right开始向两边扩散。扩散条件三个条件必须同时满足left0rightlen(s)s[left]s[right]满足条件left-1right1继续扩散。为什么最后要回退例如aba扩散过程left1 right1 ↓ left0 right2 ↓ left-1 right3退出循环时left-1 right3已经越界了。真正有效的边界应该是0 ~ 2因此返回left1right-1六、完整代码classSolution:deflongestPalindrome(self,s:str)-str:# 长度小于2直接返回iflen(s)2:returns start0end0defexpand(left,right):while(left0andrightlen(s)ands[left]s[right]):left-1right1returnleft1,right-1foriinrange(len(s)):# 奇数长度回文l1,r1expand(i,i)# 偶数长度回文l2,r2expand(i,i1)# 更新最长奇数回文ifr1-l1end-start:startl1 endr1# 更新最长偶数回文ifr2-l2end-start:startl2 endr2returns[start:end1]七、拿示例跑一遍字符串s babadi 0奇数b长度1偶数无最长bi 1奇数bab长度3更新答案bab偶数无i 2奇数aba长度3和当前最长相同。保持bab最终返回bab八、为什么i 1不会越界假设s abc最后一次i2expand(2,3)进入函数rightlen(s)即33不成立。直接退出。不会报错。九、复杂度分析时间复杂度O(n²)共有2n 个中心每个中心最多扩散O(n)因此O(n²)空间复杂度O(1)只使用有限几个变量。十、高频易错点1、只处理奇数回文错误expand(i,i)遗漏expand(i,i1)会导致cbbd输出错误。2、扩散使用 if错误ifs[left]s[right]:只能扩一层。必须使用while持续扩散。3、忘记回退边界错误returnleft,right应该returnleft1,right-14、长度公式少写 1错误right-left正确right-left15、字符串切片忘记1错误s[start:end]正确s[start:end1]因为 Python 切片左闭右开十一、一句话总结最长回文子串的核心思想枚举每一个可能的回文中心从中心向两边不断扩散记录最长回文的左右边界。记忆口诀一个字符找奇数 两个字符找偶数 左右不断往外扩 记录最长回文串。

相关新闻

终极指南：如何在Windows 10/11上轻松安装Android子系统（WSABuilds完整教程）
2026/6/30 13:00:29

终极指南：如何在Windows 10/11上轻松安装Android子系统（WSABuilds完整教程）

终极指南：如何在Windows 10/11上轻松安装Android子系统（WSABuilds完整教程） 【免费下载链接】WSABuilds Run Windows Subsystem For Android on your Windows 10 and Windows 11 PC using prebuilt binaries with Google Play Store (MindThe…

阅读更多
拒绝级联雪崩：基于控制论与BBR自适应降载重构wechatapi弹性网关
2026/6/30 13:00:29

拒绝级联雪崩：基于控制论与BBR自适应降载重构wechatapi弹性网关

在基于 wechatapi（个人微信API）构建超大规模社群矩阵或深度依赖本地 LLM（大语言模型）的复杂系统中，网关的吞吐能力极易受到宿主机硬件资源的动态制约。传统的静态限流（如令牌桶、漏桶算法）采用硬…

阅读更多
STM32增量式PID直流电机调速实战：从原理到源码解析
2026/6/30 13:00:29

STM32增量式PID直流电机调速实战：从原理到源码解析

1. 硬件选型与电路搭建 搞过电机控制的朋友都知道，硬件选型是项目成败的第一步。我这次用的主控是STM32F103C8T6，也就是大家常说的"蓝 pill"板，性价比高到离谱，某宝20块钱就能拿下。驱动芯片选的TB6612，这玩…

阅读更多
Fable 5阉割 vs Sol切脑，谁更狠 - 微元算力(weytoken)
2026/6/30 14:00:29

Fable 5阉割 vs Sol切脑，谁更狠 - 微元算力(weytoken)

摘要：2026年6月，Fable 5发布72小时后全球禁用，GPT-5.6 Sol被限制在"获批名单"——两大最强模型同时被安全护栏摁住，但路径截然不同。Anthropic采用"动态降级"：所有人用同一模型，触发护…

阅读更多
@Transactional注解
2026/6/30 14:00:29

@Transactional注解

Transactional注解一、 核心工作原理二、 关键属性详解三、 常见失效场景与避坑指南四、 总结建议Transactional 是 Spring 框架中实现声明式事务管理的核心注解。它通过 AOP（面向切面编程）动态代理机制，将事务的开启、提交、回滚逻辑从业务代…

阅读更多
学习通Windows原生客户端底层实现与高负载场景稳定性分析
2026/6/30 14:00:29

学习通Windows原生客户端底层实现与高负载场景稳定性分析

一、问题的起点 学习通在Windows平台有两个运行路径：Microsoft Store原生客户端和安卓模拟器方案。从CSDN的技术视角来看，这个选择不是一个"哪个好用"的主观问题，而是一个运行时架构差异导致的稳定性问题。 本文从内存模型、渲染…

阅读更多
wvp-GB28181-pro深度解析：基于Java的国标视频监控平台架构设计与高并发实现
2026/6/30 14:00:29

wvp-GB28181-pro深度解析：基于Java的国标视频监控平台架构设计与高并发实现

wvp-GB28181-pro深度解析：基于Java的国标视频监控平台架构设计与高并发实现 【免费下载链接】wvp-GB28181-pro 基于GB28181-2016、部标808、部标1078标准实现的开箱即用的网络视频平台。自带管理页面，支持NAT穿透，支持海康、大华、宇视等品牌…

阅读更多
EMI滤波电感五大核心参数完整选型
2026/6/30 14:00:29

EMI滤波电感五大核心参数完整选型

多数硬件工程师筛选滤波电感时，习惯仅以标称电感量作为选型依据，殊不知电感量只是基础指标，直流电阻 DCR、饱和电流 Isat、自谐振频率 SRF、阻抗频率特性、额定温升电流五大参数，直接决定滤波电路长期稳定性与 EMI 抑制上限&#…

阅读更多
LeetCode 5. 最长回文子串——中心扩展法彻底讲透
2026/6/30 13:00:29

LeetCode 5. 最长回文子串——中心扩展法彻底讲透

LeetCode 5. 最长回文子串——中心扩展法彻底讲透 一、题目描述 给定一个字符串 s，找到其中最长的回文子串，并返回这个子串。 示例： 输入：s "babad" 输出："bab" 解释："aba"…

阅读更多
AI Coding 六个月真实ROI账本：产品经理的血泪教训，研发的冷静忠告
2026/6/28 0:00:11

AI Coding 六个月真实ROI账本：产品经理的血泪教训，研发的冷静忠告

6个月前的2025年12月，Boris Cherny 公开宣布自己卸载了 IDE。一时间，Vibe Coding 成了全行业最热的话题。6个月后，当我们回过头来拉一份真实账本，发现事情远没有"一句话生成一个App"那么浪漫。本文从产品经理和研发两个…

阅读更多
审计来了，数据权限全开——审计走了，怎么确保权限全部关掉？
2026/6/28 0:00:11

审计来了，数据权限全开——审计走了，怎么确保权限全部关掉？

引言：审计结束三个月了，审计员的权限还没关某城商行每年按照监管要求开展至少一次数据安全审计。审计期间，内审部门需要抽样检查各类业务数据——交易流水、客户信息、员工操作日志、权限配置记录。这些数据分布在不同系统中，审计…

阅读更多
如何在1分钟内为Windows安装苹果USB网络共享驱动：完整解决方案
2026/6/30 0:00:27

如何在1分钟内为Windows安装苹果USB网络共享驱动：完整解决方案

如何在1分钟内为Windows安装苹果USB网络共享驱动：完整解决方案 【免费下载链接】Apple-Mobile-Drivers-Installer Powershell script to easily install Apple USB and Mobile Device Ethernet (USB Tethering) drivers on Windows! 项目地址: https://gitcode.co…

阅读更多
AScript异步执行与await关键字
2026/6/30 0:00:27

AScript异步执行与await关键字

、异步解析执行 AScript提供了 Script.EvalAsync 异步方法，异步执行脚本，可设置 CancellationToken 参数。 AScript执行模式有解析执行和编译执行两种模式，这两种模式下的异步执行又有所不同： 1）解析执行模式&#…

阅读更多
AI时代真的风水轮流转，前段时间最火的还是Claude Code,转眼间Codex就火得一塌糊涂。Codex是由OpenAI 推出的AI智能体。
2026/6/30 0:00:27

AI时代真的风水轮流转，前段时间最火的还是Claude Code,转眼间Codex就火得一塌糊涂。Codex是由OpenAI 推出的AI智能体。

它不仅能回答问题，编写代码，还能读取电脑本地文件，修改项目，浏览网页，调用外部工具，自动化执行任务，操作浏览器甚至桌面应用。 也是早早的就给身边不是程序员的亲朋好友安利了，都是用…

阅读更多
GIT修改用户名
2026/6/28 5:47:46

GIT修改用户名

在GIT中修改用户名可按以下步骤操作： 查看当前git的用户名，使用命令git config --list或git config user.name。修改git用户名，使用命令git config --global user.name "xxx（新的用户名）"，将其中…

阅读更多
Win11Debloat：让你的Windows系统重获新生的终极优化工具
2026/6/28 14:44:43

Win11Debloat：让你的Windows系统重获新生的终极优化工具

Win11Debloat：让你的Windows系统重获新生的终极优化工具 【免费下载链接】Win11Debloat A simple, lightweight PowerShell script that allows you to remove pre-installed apps, disable telemetry, as well as perform various other changes to declutter and …

阅读更多
技术深度解析：m4s-converter实现原理与B站缓存视频转换最佳实践
2026/6/28 14:44:39

技术深度解析：m4s-converter实现原理与B站缓存视频转换最佳实践

技术深度解析：m4s-converter实现原理与B站缓存视频转换最佳实践 【免费下载链接】m4s-converter 一个跨平台小工具，将bilibili缓存的m4s格式音视频文件合并成mp4 项目地址: https://gitcode.com/gh_mirrors/m4/m4s-converter m4s-converter是一个…

阅读更多