1. 最长回文子串问题解析回文串Palindrome是指正读反读都相同的字符串比如aba、abba都是典型的回文串。寻找字符串中的最长回文子串是算法面试中的经典问题也是力扣hot100中的第5题。这个问题看似简单但蕴含着丰富的算法思想。在实际应用中回文检测常用于文本处理、DNA序列分析等领域。比如在基因组学中回文结构往往与特定的生物功能相关在自然语言处理中回文检测可用于识别特定类型的修辞手法。注意回文子串与回文子序列是不同的概念。子串要求字符必须连续而子序列则不要求连续。这是面试中常见的混淆点。2. 暴力解法与优化思路2.1 暴力解法分析最直观的解法是枚举所有可能的子串然后检查是否为回文。对于一个长度为n的字符串子串总数为O(n²)每个子串检查回文需要O(n)时间因此总时间复杂度为O(n³)。def longestPalindrome(s: str) - str: n len(s) if n 2: return s max_len 1 begin 0 for i in range(n-1): for j in range(i1, n): if j-i1 max_len and self.is_palindrome(s, i, j): max_len j-i1 begin i return s[begin:beginmax_len] def is_palindrome(s, left, right): while left right: if s[left] ! s[right]: return False left 1 right - 1 return True这种解法虽然简单但在力扣上提交时会因为时间复杂度过高而无法通过所有测试用例。我们需要寻找更高效的算法。2.2 中心扩展法中心扩展法的核心思想是每个回文串都有一个中心从这个中心向两边扩展判断两侧字符是否相同。对于长度为n的字符串有2n-1个可能的中心因为中心可以是一个字符也可以是两个字符之间。def longestPalindrome(s: str) - str: if not s or len(s) 1: return start 0 end 0 for i in range(len(s)): len1 expandAroundCenter(s, i, i) # 奇数长度 len2 expandAroundCenter(s, i, i1) # 偶数长度 max_len max(len1, len2) if max_len end - start: start i - (max_len - 1) // 2 end i max_len // 2 return s[start:end1] def expandAroundCenter(s, left, right): while left 0 and right len(s) and s[left] s[right]: left - 1 right 1 return right - left - 1这种方法将时间复杂度降到了O(n²)空间复杂度为O(1)是解决这个问题的一个有效方法。3. Manacher算法详解3.1 算法原理Manacher算法可以在O(n)时间内解决最长回文子串问题。它的核心思想是利用已知的回文信息来避免重复计算。算法通过维护一个回文半径数组P其中P[i]表示以i为中心的最长回文半径。算法步骤如下预处理字符串在字符间插入特殊字符如#将奇偶长度统一处理维护当前已知的最右回文边界R及其中心C对于每个位置i利用对称性快速计算初始P[i]中心扩展更新P[i]更新R和C3.2 代码实现def longestPalindrome(s: str) - str: # 预处理字符串 T #.join(^{}$.format(s)) n len(T) P [0] * n C R 0 for i in range(1, n-1): # 利用对称性快速初始化P[i] if i R: P[i] min(R - i, P[2*C - i]) # 中心扩展 while T[i P[i] 1] T[i - P[i] - 1]: P[i] 1 # 更新中心和右边界 if i P[i] R: C, R i, i P[i] # 找出P中的最大值 max_len, center max((n, i) for i, n in enumerate(P)) return s[(center - max_len)//2 : (center max_len)//2]Manacher算法虽然效率高但实现起来较为复杂在面试中通常只需要解释思路即可。中心扩展法在大多数情况下已经足够。4. 动态规划解法4.1 状态定义与转移方程动态规划是解决回文问题的另一种思路。我们定义dp[i][j]表示字符串s从i到j的子串是否为回文。状态转移方程dp[i][j] True, 如果i j单个字符dp[i][j] (s[i] s[j]), 如果j i 1两个字符dp[i][j] (s[i] s[j]) and dp[i1][j-1], 其他情况4.2 实现代码def longestPalindrome(s: str) - str: n len(s) if n 2: return s dp [[False] * n for _ in range(n)] max_len 1 start 0 # 所有长度为1的子串都是回文 for i in range(n): dp[i][i] True # 检查长度为2的子串 for i in range(n-1): if s[i] s[i1]: dp[i][i1] True start i max_len 2 # 检查长度大于2的子串 for length in range(3, n1): for i in range(n - length 1): j i length - 1 if s[i] s[j] and dp[i1][j-1]: dp[i][j] True if length max_len: start i max_len length return s[start:startmax_len]动态规划解法的时间复杂度为O(n²)空间复杂度也是O(n²)相比中心扩展法需要更多的空间。5. 算法比较与选择5.1 时间复杂度对比算法时间复杂度空间复杂度适用场景暴力解法O(n³)O(1)仅适用于非常短的字符串中心扩展O(n²)O(1)面试中最常要求的解法ManacherO(n)O(n)需要极致性能的场景动态规划O(n²)O(n²)需要记录所有子串信息时5.2 面试中的选择策略在力扣面试或hot100刷题时建议优先掌握中心扩展法因为实现相对简单不易出错时间复杂度在大多数情况下已经足够可以逐步扩展到更复杂的问题Manacher算法虽然高效但实现复杂除非特别要求一般不需要在面试中实现完整代码但可以讨论其思路。6. 常见错误与调试技巧6.1 边界条件处理回文问题容易在边界条件上出错特别是空字符串或单字符字符串全相同字符的字符串如aaaaa没有回文子串长于1的情况如abc调试技巧在实现算法前先手动计算几个简单测试用例的预期结果包括上述边界情况。6.2 下标越界问题中心扩展法和Manacher算法中都涉及下标操作容易出现数组越界。解决方法在字符串前后添加哨兵字符如^和$在while循环中严格检查下标范围6.3 性能优化当字符串很长时可以添加一些提前终止的条件如果剩余未检查的字符串长度小于当前找到的最大回文长度可以直接终止对于大量重复字符的字符串可以进行压缩处理7. 力扣刷题建议7.1 同类问题扩展掌握最长回文子串后可以尝试解决力扣上的其他回文问题回文子串统计所有回文子串数量最长回文子序列注意子序列与子串的区别分割回文串回溯算法应用7.2 刷题策略对于hot100这类高频题库先理解问题手动计算简单例子尝试暴力解法再思考优化比较不同解法的优劣总结解题模板和常见陷阱定期复习特别是面试前7.3 代码模板中心扩展法的通用模板def longestPalindrome(s): def expand(l, r): while l 0 and r len(s) and s[l] s[r]: l - 1 r 1 return r - l - 1 start end 0 for i in range(len(s)): len1 expand(i, i) len2 expand(i, i1) max_len max(len1, len2) if max_len end - start: start i - (max_len - 1) // 2 end i max_len // 2 return s[start:end1]记住这个模板可以快速解决大多数回文子串问题。
