1 中文题目

给你一个字符串 $s$，找到 $s$ 中最长的回文子串。回文串是一个正读和反读都相同的字符串.

示例 1：

• 输入：$s="babad"$
• 输出：$"bab"$
• 解释：$"aba"$同样是符合题意的答案。

示例 2：

• 输入：$s="cbbd"$
• 输出：$"bb"$

提示：

• $1\le s.length\le 1000$
• $s$ 仅由数字和英文字母组成

---

2 求解思路

2.1 基础解法：暴力解法

思路
遍历所有可能的子串，对每个子串判断是否为回文串，并更新最长回文串的信息

• 步骤1: 外层循环确定子串起始位置
• 步骤2: 内层循环确定子串结束位置
• 步骤3: 判断当前子串是否为回文串
• 步骤4: 如果是回文串且长度更长，则更新记录
• 步骤5: 返回最长的回文子串

Python代码

class Solution:def longestPalindrome(self, s: str) -> str:"""寻找字符串中的最长回文子串 - 暴力解法Args:s: 输入字符串Returns:返回最长的回文子串"""def isPalindrome(start: int, end: int) -> bool:"""判断子串是否为回文串的辅助函数Args:start: 子串的起始索引end: 子串的结束索引Returns:如果是回文串返回True，否则返回False"""# 使用双指针从两端向中间移动while start < end:# 如果对应位置的字符不相等，则不是回文串if s[start] != s[end]:return False# 向中间移动start += 1end -= 1return True# 获取字符串长度n = len(s)# 特殊情况处理：空串或单字符if n < 2:return s# 记录最长回文子串的长度max_len = 1# 记录最长回文子串的起始位置start = 0# 外层循环：子串的起始位置for i in range(n):# 内层循环：子串的结束位置for j in range(i + 1, n):# 当前子串长度sub_len = j - i + 1# 如果当前子串长度大于已知最大长度，并且是回文串if sub_len > max_len and isPalindrome(i, j):# 更新最大长度和起始位置max_len = sub_lenstart = i# 返回最长回文子串return s[start:start + max_len]

时空复杂度分析

• 时间复杂度分析
  • 外层循环，遍历所有起始位置：$O(n)$
  • 内层循环，对每个起始位置遍历所有可能的结束位置：$O(n)$
  • 判断回文：$O(n)$

总复杂度：$O(n)\ast O(n)\ast O(n)=O(n^3)$

• 空间复杂度分析：O(1)
  • 只使用了常数个变量
  • 不需要额外的数组或矩阵
  • 没有递归调用栈

---

2.2 优化解法：中心拓展法

思路
回文串是以中心点对称的，从每个可能的中心点向两边扩展，分别处理奇数长度和偶数长度的情况

• 步骤1: 遍历每个可能的中心点
• 步骤2: 对每个中心点，分别处理奇数和偶数长度的情况
• 步骤3: 从中心向两边扩展，直到不满足回文条件
• 步骤4: 记录并更新最长回文子串的位置
• 步骤5: 返回最长的回文子串

python代码

class Solution:def longestPalindrome(self, s: str) -> str:"""使用中心扩展法查找最长回文子串Args:s: 输入字符串Returns:返回最长的回文子串"""def expandAroundCenter(left: int, right: int) -> tuple:"""从中心向两端扩展，寻找最长回文子串Args:left: 左边界起始位置right: 右边界起始位置Returns:返回扩展后的左右边界位置"""# 当左右指针都在有效范围内，且对应字符相等时继续扩展while left >= 0 and right < len(s) and s[left] == s[right]:# 向左扩展left -= 1# 向右扩展right += 1# 返回最后一次有效的回文串边界# left + 1: 因为while循环中left多减了1# right - 1: 因为while循环中right多加了1return left + 1, right - 1# 特殊情况处理if not s or len(s) < 2:return s# 记录最长回文子串的起始和结束位置start = 0end = 0# 遍历每个可能的中心点for i in range(len(s)):# 处理奇数长度的回文串，以单个字符为中心left1, right1 = expandAroundCenter(i, i)# 处理偶数长度的回文串，以两个字符之间的空隙为中心left2, right2 = expandAroundCenter(i, i + 1)# 更新最长回文子串的位置# 比较当前找到的两种回文串和之前找到的回文串的长度if right1 - left1 > end - start:start, end = left1, right1if right2 - left2 > end - start:start, end = left2, right2# 返回最长回文子串return s[start:end + 1]

时空复杂度分析

• 时间复杂度分析：$O(n^2)$
  • 遍历中心点，奇数长度共有n个可能的中心点；偶数长度共有n-1个可能的中心点：$O(n)$
  • 中心扩展，每次扩展最多需要n/2次比较：$O(n)$

总复杂度：$O(n)\ast O(n)=O(n^2)$

• 空间复杂度分析：$O(1)$
  • 只需要常数个变量记录位置信息
  • 不需要额外的数组或矩阵
  • 没有递归调用栈

---

2.3 最优解法：Manacher算法

思路
通过预处理将所有可能的中心点变成奇数形式，利用回文串的对称性质避免重复计算，记录并复用之前计算的结果。

• 步骤1: 字符串预处理
  • 在字符间插入特殊字符’#’
  • 统一奇偶长度的回文串处理方式
• 步骤2: 初始化状态
  • 初始化p数组
  • 设置center和right初始值
• 步骤3: 遍历处理每个位置
  • 利用对称性获取初始回文半径
  • 进行中心扩展
  • 更新最大右边界和中心点
  • 更新最长回文串信息
• 步骤4: 还原结果
  • 将处理后的结果转换回原始字符串

python代码

class Solution:def longestPalindrome(self, s: str) -> str:"""使用Manacher算法查找最长回文子串Args:s: 输入字符串Returns:返回最长的回文子串"""# 特殊情况处理if not s or len(s) < 2:return s# Step 1: 预处理字符串，插入特殊字符 '#'# 例如："abc" -> "#a#b#c#"t = '#' + '#'.join(s) + '#'n = len(t)# p[i]数组记录以i为中心的回文半径（不包括中心点）p = [0] * n# 维护已找到的回文子串的最右边界right及其对应的中心点centercenter = 0  # 当前最大回文串的中心位置right = 0   # 当前最大回文串的右边界# 记录最长回文串的相关信息max_len = 0  # 最长回文串的长度max_center = 0  # 最长回文串的中心位置# Step 2: 核心算法部分for i in range(n):if i < right:# 利用回文串的对称性，获取初始回文半径# mirror是i关于center的对称点mirror = 2 * center - i# 避免超出right边界，取较小值p[i] = min(right - i, p[mirror])# Step 3: 中心扩展# 尝试扩展回文串的范围left = i - (p[i] + 1)  # 当前回文串的左边界r = i + (p[i] + 1)     # 当前回文串的右边界# 在不越界的情况下继续扩展while left >= 0 and r < n and t[left] == t[r]:p[i] += 1left -= 1r += 1# Step 4: 更新right和center# 如果新的回文串的右边界超过了当前的rightif i + p[i] > right:center = iright = i + p[i]# Step 5: 更新最长回文串的信息if p[i] > max_len:max_len = p[i]max_center = i# Step 6: 还原原始字符串中的回文子串# 去除特殊字符'#'，计算在原字符串中的起始位置和长度start = (max_center - max_len) // 2return s[start: start + max_len]

时空复杂度分析

• 时间复杂度分析
  • 预处理字符串：$O(n)$
  • 主循环处理：$O(n)$
  • 中心扩展：均摊$O(1)$

时间总体复杂度：$O(n)$

• 空间复杂度分析：$O(n)$
  • p数组：$O(n)$
  • 预处理后的字符串：$O(n)$
  • 其他变量：$O(1)$

总空间复杂度：$O(n)$

---

3 题目总结

题目难度： 中等
数据结构： 字符串
应用算法：Manacher算法、双指针