👤作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、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, 0 for i in range(len(s)): # 以 s[i] 为中心的最长回文子串的长度 len1 = expandAroundCenter(s, i, i) # 以 s[i] 和 s[i+1] 为中心的最长回文子串的长度 len2 = expandAroundCenter(s, i, i + 1) # 两种情况中的较大值 maxLen = max(len1, len2) if maxLen > end - start: start = i - (maxLen - 1) // 2 end = i + maxLen // 2 return 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 -= 1 right += 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] * n center = right = 0 max_len = max_center = 0 for 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和right if 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) // 2 return 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算法都是解决“最长回文子串”问题的有效方法。然而，无论是哪种方法，在实现时都需要小心处理边界条件、索引计算和特殊情况。熟悉这些坑并学会如何避免，可以帮助编程者写出更加准确和高效的代码。
欢迎关注微信公众号 数据分析螺丝钉
