leetcode 5. 最长回文子串 -中心扩展算法
2021/9/26 1:11:00
本文主要是介绍leetcode 5. 最长回文子串 -中心扩展算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
给你一个字符串 s,找到 s 中最长的回文子串。
示例 1:
输入:s = “babad”
输出:“bab”
解释:“aba” 同样是符合题意的答案。
示例 2:
输入:s = “cbbd”
输出:“bb”
示例 3:
输入:s = “a”
输出:“a”
示例 4:
输入:s = “ac”
输出:“a”
提示:
1 <= s.length <= 1000
s 仅由数字和英文字母(大写和/或小写)组成
class Solution: def longestPalindrome(self, s: str) -> str: start = 0 end = 0 def expend_center(i, j ,s): while i >= 0 and j < len(s) and s[i] == s[j]: i -= 1 j += 1 return i + 1, j - 1 for i in range(len(s)): left1, right1 = expend_center(i, i, s) left2, right2 = expend_center(i, i + 1, s) if right1 - left1 > end - start: start, end = left1, right1 if right2 - left2 > end - start: start, end = left2, right2 return s[start:end + 1]
举例:aba
从a开始向两边扩展,因为触发左边界跳出
继续从a,b开始从两边扩展,因为a,b不相同则直接退出
从b开始向两边扩展,s[0]与s[1]都是a相同,则说明现在的最长长度是3
从b,a向两边扩展,右侧触边,则退出
从s[2],a开始像两边扩展,右侧触边,则退出。
边界情况即为子串长度为 1或 2的情况。我们枚举每一种边界情况,并从对应的子串开始不断地向两边扩展。如果两边的字母相同,我们就可以继续扩展,例如从 P(i+1,j-1)P(i+1,j−1) 扩展到 P(i,j)P(i,j);如果两边的字母不同,我们就可以停止扩展,因为在这之后的子串都不能是回文串了。
聪明的读者此时应该可以发现,「边界情况」对应的子串实际上就是我们「扩展」出的回文串的「回文中心」。方法二的本质即为:我们枚举所有的「回文中心」并尝试「扩展」,直到无法扩展为止,此时的回文串长度即为此「回文中心」下的最长回文串长度。我们对所有的长度求出最大值,即可得到最终的答案。
空间复杂度为o(1),因为使用的是常量的变量,时间复杂度为o(n^2),因为从中间往两边的中心点可能是1个,也可能是两个,一共有n,n-1中可能,每一种像外扩展o(n)。
这篇关于leetcode 5. 最长回文子串 -中心扩展算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2025-01-12深入理解 ECMAScript 2024 新特性:Map.groupBy() 分组操作
- 2025-01-11国产医疗级心电ECG采集处理模块
- 2025-01-10Rakuten 乐天积分系统从 Cassandra 到 TiDB 的选型与实战
- 2025-01-09CMS内容管理系统是什么?如何选择适合你的平台?
- 2025-01-08CCPM如何缩短项目周期并降低风险?
- 2025-01-08Omnivore 替代品 Readeck 安装与使用教程
- 2025-01-07Cursor 收费太贵?3分钟教你接入超低价 DeepSeek-V3,代码质量逼近 Claude 3.5
- 2025-01-06PingCAP 连续两年入选 Gartner 云数据库管理系统魔力象限“荣誉提及”
- 2025-01-05Easysearch 可搜索快照功能,看这篇就够了
- 2025-01-04BOT+EPC模式在基础设施项目中的应用与优势