LeetCode 5 最长回文子串：python3 题解

题目链接：5. 最长回文子串

目录

• 1. 题目理解
  
• 2. 解题思路与方法讨论
  
  
  
  • 方法一：中心扩展法 (Expand Around Center)
    
  • 方法二：动态规划 (Dynamic Programming)
    
  • 方法三：Manacher 算法 (马拉车算法)
    
  
  
• 3. 代码实现 (中心扩展法)
  
• 4. 代码实现 (动态规划法)
  
• 5. 复杂度分析
  
• 6. 总结与建议
  

1. 题目理解

题目目标：
给定一个字符串 s，你需要找到它里面最长的一个子串，这个子串必须是回文的。
关键概念：

• 子串 (Substring)：字符串中连续的一段字符。例如 "babad" 中，"bab" 是子串，但 "bd" 不是（因为不连续）。
  
• 回文 (Palindrome)：正着读和反着读都一样的字符串。例如 "aba", "bb", "a" 都是回文。
  

示例分析：

• 输入 "babad" -> 输出 "bab" 或 "aba"。
  
• 输入 "cbbd" -> 输出 "bb"。
  

数据范围：
字符串长度 1  int:            # 当 left 和 right 在合法范围内，且字符相等时，继续向两边扩展            while left >= 0 and right < n and s[left] == s[right]:                left -= 1                right += 1            # 循环结束时，s[left] != s[right] 或者越界了            # 所以实际的回文长度是 (right - 1) - (left + 1) + 1 = right - left - 1            return right - left - 1                # 遍历字符串的每一个位置，将其视为“中心”        for i in range(n):            # 情况 1：以 s 为中心，检查奇数长度的回文 (如 "aba")            # 此时左右指针都从 i 开始            len1 = expand_around_center(i, i)                        # 情况 2：以 s 和 s[i+1] 之间为中心，检查偶数长度的回文 (如 "abba")            # 此时左指针从 i 开始，右指针从 i+1 开始            len2 = expand_around_center(i, i + 1)                        # 取两种情况中的较大值            current_max = max(len1, len2)                        # 如果发现的回文比之前记录的更长，则更新 start 和 max_len            if current_max > max_len:                max_len = current_max                # 计算新的起始位置                # 推导公式：起始位置 = 当前中心 i - (新长度 - 1) // 2                # 例如：中心 i=2, 长度 3 ("aba"), start = 2 - 1 = 1                # 例如：中心 i=1, 长度 4 ("abba"), start = 1 - 1 = 0                start = i - (current_max - 1) // 2                # 返回切片，注意切片是左闭右开，所以结束位置是 start + max_len        return s[start : start + max_len][/code]4. 代码实现 (动态规划法)

为了更全面地理解，这里也提供动态规划的代码。虽然空间消耗大，但逻辑非常经典。

1. class Solution:
2.     def longestPalindrome(self, s: str) -> str:
3.         # 获取字符串长度
4.         n = len(s)
5.         
6.         # 边界情况：如果字符串长度小于 2，它本身就是最长回文
7.         if n < 2:
8.             return s
9.         
10.         # 记录最长回文子串的起始位置 (start) 和长度 (max_len)
11.         # 初始化为 0 和 1，因为单个字符肯定是回文
12.         start = 0
13.         max_len = 1
14.         
15.         # 定义一个辅助函数，用于从中心向两边扩展
16.         # left 和 right 是中心的左右边界索引
17.         def expand_around_center(left: int, right: int) -> int:
18.             # 当 left 和 right 在合法范围内，且字符相等时，继续向两边扩展
19.             while left >= 0 and right < n and s[left] == s[right]:
20.                 left -= 1
21.                 right += 1
22.             # 循环结束时，s[left] != s[right] 或者越界了
23.             # 所以实际的回文长度是 (right - 1) - (left + 1) + 1 = right - left - 1
24.             return right - left - 1
25.         
26.         # 遍历字符串的每一个位置，将其视为“中心”
27.         for i in range(n):
28.             # 情况 1：以 s[i] 为中心，检查奇数长度的回文 (如 "aba")
29.             # 此时左右指针都从 i 开始
30.             len1 = expand_around_center(i, i)
31.             
32.             # 情况 2：以 s[i] 和 s[i+1] 之间为中心，检查偶数长度的回文 (如 "abba")
33.             # 此时左指针从 i 开始，右指针从 i+1 开始
34.             len2 = expand_around_center(i, i + 1)
35.             
36.             # 取两种情况中的较大值
37.             current_max = max(len1, len2)
38.             
39.             # 如果发现的回文比之前记录的更长，则更新 start 和 max_len
40.             if current_max > max_len:
41.                 max_len = current_max
42.                 # 计算新的起始位置
43.                 # 推导公式：起始位置 = 当前中心 i - (新长度 - 1) // 2
44.                 # 例如：中心 i=2, 长度 3 ("aba"), start = 2 - 1 = 1
45.                 # 例如：中心 i=1, 长度 4 ("abba"), start = 1 - 1 = 0
46.                 start = i - (current_max - 1) // 2
47.         
48.         # 返回切片，注意切片是左闭右开，所以结束位置是 start + max_len
49.         return s[start : start + max_len]

复制代码

5. 复杂度分析

针对推荐的 中心扩展法：

• 时间复杂度: \(O(N^2)\)
  
  
  
  • 外层循环遍历了 \(N\) 个字符。
    
  • 内层 expand_around_center 函数在最坏情况下（如整个字符串都是 'a'）会扩展 \(O(N)\) 次。
    
  • 总操作次数约为 \(N \times N\)。
    
  
  
• 空间复杂度: \(O(1)\)
  
  
  
  • 我们只使用了几个变量 (start, max_len, i, left, right) 来存储状态。
    
  • 没有使用额外的数组或矩阵（除了输入字符串本身）。
    
  
  

针对 动态规划法：

• 时间复杂度: \(O(N^2)\)
  
  
  
  • 需要填充一个 \(N \times N\) 的表格。
    
  
  
• 空间复杂度: \(O(N^2)\)
  
  
  
  • 需要存储 \(N \times N\) 的布尔值表格。
    
  
  

6. 总结与建议

• 首选方案：在面试或实际刷题中，中心扩展法是最佳选择。它在时间和空间上取得了很好的平衡，且代码比 Manacher 算法简单得多，比动态规划节省空间。
  
• 理解难点：
  
  
  
  • 为什么要检查两次中心（i, i 和 i, i+1）？
    
    
    
    • 答：因为回文串长度可能是奇数（有明确中心字符）或偶数（中心在两个字符之间）。
      
    
    
  • start 索引如何计算？
    
    
    
    • 答：start = i - (current_max - 1) // 2。这是通过数学推导得出的，建议通过画图和示例（如 "aba" 和 "abba"）来手动验证一下，加深记忆。
      
    
    
  
  
• 边界处理：
  
  
  
  • 代码开头处理了 n < 2 的情况，这是为了防止后续逻辑出错，也提高了短字符串的效率。
    
  • expand_around_center 中的 while 循环条件 left >= 0 and right < n 防止了数组越界。
    
  
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！