LeetCode【0005】最长回文子串

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 += 1
                end -= 1
            return 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_len
                    start = 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多加了1
            return left + 1, right - 1
        
        # 特殊情况处理
        if not s or len(s) < 2:
            return s
            
        # 记录最长回文子串的起始和结束位置
        start = 0
        end = 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, right1
            if 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及其对应的中心点center
        center = 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] += 1
                left -= 1
                r += 1
            
            # Step 4: 更新right和center
            # 如果新的回文串的右边界超过了当前的right
            if i + p[i] > right:
                center = i
                right = i + p[i]
            
            # Step 5: 更新最长回文串的信息
            if p[i] > max_len:
                max_len = p[i]
                max_center = i
        
        # Step 6: 还原原始字符串中的回文子串
        # 去除特殊字符'#'，计算在原字符串中的起始位置和长度
        start = (max_center - max_len) // 2
        return 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算法、双指针

原文地址：https://blog.csdn.net/qq_32882309/article/details/143673009

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！