小米官方网站开发版在哪里,网站建设网络推广的好处,路边社 wordpress,我想在购物网站做代理#x1f464;作者介绍#xff1a;10年大厂数据\经营分析经验#xff0c;现任大厂数据部门负责人。 会一些的技术#xff1a;数据分析、算法、SQL、大数据相关、python 作者专栏每日更新#xff1a; LeetCode解锁1000题:打怪升级之旅 python数据分析可视化:企业实战案例 备… 作者介绍10年大厂数据\经营分析经验现任大厂数据部门负责人。 会一些的技术数据分析、算法、SQL、大数据相关、python 作者专栏每日更新 LeetCode解锁1000题:打怪升级之旅 python数据分析可视化:企业实战案例 备注说明方便大家阅读统一使用python带必要注释公众号 数据分析螺丝钉 一起打怪升级 “最长回文子串”是一个经典而广为人知的问题它要求找到一个字符串中最长的回文子串。回文是一种正读和反读都相同的字符串例如 “madam” 或 “racecar”。
问题描述
给定一个字符串 s找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例
输入: babad
输出: bab
注意: aba 也是一个有效答案。解题思路
解决这个问题有几种不同的方法包括暴力法、动态规划、中心扩散法和Manacher算法。在这里我们主要介绍中心扩散法和Manacher算法因为它们在实际应用中更为高效。
中心扩散法
中心扩散法的核心思想是对于字符串中的每个字符尝试将其作为回文串的中心向两边扩散查找最长的回文串。
实现步骤
遍历字符串的每个字符将每个字符作为回文中心。对于每个中心向两边扩展直到不再形成回文。记录并更新最长回文子串的长度和起始位置。考虑奇数长度和偶数长度的回文分别处理。
代码示例
def longestPalindrome(s: str) - str:if not s or len(s) 1:return # 初始化最长回文子串的起始和结束索引start, end 0, 0for i in range(len(s)):# 以 s[i] 为中心的最长回文子串的长度len1 expandAroundCenter(s, i, i)# 以 s[i] 和 s[i1] 为中心的最长回文子串的长度len2 expandAroundCenter(s, i, i 1)# 两种情况中的较大值maxLen max(len1, len2)if maxLen end - start:start i - (maxLen - 1) // 2end i maxLen // 2return s[start:end 1]def expandAroundCenter(s: str, left: int, right: int) - int:# 从中心开始向两边扩散while left 0 and right len(s) and s[left] s[right]:left - 1right 1# 返回以当前中心扩散的回文子串的长度return right - left - 1# 测试代码
print(longestPalindrome(babad)) # 输出: bab 或 aba
print(longestPalindrome(cbbd)) # 输出: bb代码解读
函数 longestPalindrome • 遍历字符串对每个字符尝试两种情况的中心扩散一种是该字符自身作为中心另一种是该字符和其右邻字符共同作为中心处理偶数长度的回文。 • 使用 expandAroundCenter 函数来实现中心扩散并返回以当前中心可以扩散到的最长回文子串的长度。 • 根据返回的长度和当前遍历的字符位置更新最长回文子串的起始和结束位置。函数 expandAroundCenter • 接收字符串和两个索引代表当前考虑的中心作为参数。 • 从中心开始向两边扩散直到不能形成回文为止。 • 返回扩散后回文的长度。
特点
中心扩散法的时间复杂度为O(n^2) 其中n 是字符串的长度。空间复杂度为 O(1)因为除了输入字符串外只需要常数级别的额外空间。
尽管在最坏情况下时间复杂度较高中心扩散法因其实现简单、直观易懂而广受欢迎特别适合在面试中快速解答。对于实际应用中的字符串长度不是特别大时这种方法通常已经足够高效。
Manacher算法
Manacher 算法是一种高效的寻找字符串中最长回文子串的算法时间复杂度为 (O(n))。其主要思想是通过构建一个辅助数组来记录每个字符作为回文中心时最大的回文半径利用这些信息来避免重复的比较。
代码示例
下面是 Manacher 算法的 Python 实现
def longestPalindrome(s: str) - str:# 对原始字符串进行预处理t #.join(f^{s}$)n len(t)p [0] * ncenter right 0max_len max_center 0for i in range(1, n-1):# 利用已知的回文半径避免不必要的比较if i right:p[i] min(right - i, p[2*center - i])# 尝试扩展回文更新p[i]while t[i p[i] 1] t[i - p[i] - 1]:p[i] 1# 如果通过扩展发现更长的回文则更新center和rightif i p[i] right:center, right i, i p[i]# 更新最长回文子串的中心和长度if p[i] max_len:max_len p[i]max_center i# 根据最大回文半径和中心计算最长回文子串的起始位置和结束位置start (max_center - max_len) // 2return s[start: start max_len]# 测试代码
print(longestPalindrome(babad))
print(longestPalindrome(cbbd))代码解读
预处理为了统一处理奇数长度和偶数长度的回文首先对原字符串进行预处理每个字符间插入一个特殊字符这里使用 #同时在首尾添加特殊字符这里使用 ^ 和 $以避免边界检查回文半径数组p[i] 表示以第 i 个字符为中心的最长回文子串的半径长度。算法的核心是利用回文的对称性质通过已知的回文信息来避免重复比较。中心扩展对于每个位置 i尽量利用之前计算的 p 数组值来避免重复计算。如果 i 在当前找到的最长回文子串的右边界内可以利用其对称点的 p 值作为初始值。然后尝试向外扩展直到找到以 i 为中心的最长回文子串。更新最长回文子串信息在扩展过程中如果发现更长的回文子串更新记录的最大回文长度和对应的中心位置。结果提取:最后根据记录的最长回文子串中心和半径计算原始字符串中最长回文子串的位置并返回该子串。 Manacher 算法的巧妙之处在于通过特殊的预处理和对称性质将问题的时间复杂度优化到线性级别非常适合处理大规模字符串中的最长回文子串查找问题。
总结
中心扩散法的常见坑
1. 边界条件处理
• 在扩散过程中容易忽略字符串的边界条件。例如当左右指针移动超出字符串范围时应停止扩散。
• 解决方法在扩散前检查左右指针是否在字符串范围内。
2. 奇偶回文的处理
• 中心扩散法需要分别处理奇数长度和偶数长度的回文子串。有时可能会忽略其中一种情况从而导致结果不准确。
• 解决方法确保对每个中心点都尝试以其为中心的奇数长度和偶数长度回文扩散。
3. 更新最长回文子串时的索引计算
• 在更新最长回文子串的起始和结束索引时由于字符串索引的偏移量计算可能会出错。
• 解决方法仔细检查并正确计算基于当前中心点的最长回文子串的起始和结束索引。Manacher算法的常见坑
1. 字符串预处理
• Manacher算法的预处理步骤是在字符串的每个字符间插入一个特殊字符通常是一个不会在原字符串中出现的字符以及在首尾添加不同的特殊字符。这一步骤容易出错特别是在处理首尾字符时。
• 解决方法仔细检查预处理步骤确保正确地添加了特殊字符。
2. 回文半径数组的初始化和更新
• 在实现Manacher算法时正确初始化和更新回文半径数组 p 是关键。错误地初始化或更新 p 会导致错误的结果。
• 解决方法明确理解 p 数组的含义并确保在算法的每一步中都正确更新它。
3. 中心移动和边界更新
• 算法的核心是维护一个当前最长回文的右边界和对应的中心点。在更新这两个变量时容易出错。
• 解决方法仔细检查每次扩散后是否需要更新当前最长回文的右边界和中心点。中心扩散法和Manacher算法都是解决“最长回文子串”问题的有效方法。然而无论是哪种方法在实现时都需要小心处理边界条件、索引计算和特殊情况。熟悉这些坑并学会如何避免可以帮助编程者写出更加准确和高效的代码。
