LeetCode算法笔记5

题目描述

给你一个字符串 s，找到 s 中最长的 回文子串

示例 1：

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

示例 2：

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

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

解法:

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) < 2:
            return s
        
        start, end = 0, 0
        
        def expand_around_center(left, right):
            nonlocal start, end
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            # 注意：此时s[left] != s[right]，回文串范围为[left+1, right-1]
            if right - left - 1 > end - start:
                start = left + 1
                end = right - 1
        
        for i in range(len(s)):
            expand_around_center(i, i)        # 以单个字符为中心扩展
            expand_around_center(i, i + 1)    # 以两个字符为中心扩展
        
        return s[start:end + 1]

详细思路

 解释优化后的中心扩展法寻找最长回文子串的代码：

1. 初始检查：

   • 如果输入字符串 s 的长度小于 2，直接返回 s，因为单个字符或空字符串本身就是回文。

2. 变量初始化：

   • start 和 end 初始化为 0。它们用来记录当前找到的最长回文子串的起始和结束索引。

3. expand_around_center 函数：

   • 这个函数用于以给定的 left 和 right 为中心向两边扩展，尝试找到更长的回文子串。
   • left 和 right 分别代表当前扩展的左右边界。
   • 使用 while 循环来检查当前 left 和 right 对应的字符是否相等，并且 left 和 right 在有效范围内。
   • 当不再构成回文（即 s[left] != s[right]）时，退出循环。此时找到的回文子串的范围为 [left+1, right-1]。
   • 如果当前找到的回文子串长度大于之前记录的最长回文子串长度（即 right - left - 1 > end - start），则更新 start 和 end。

4. 遍历所有可能的中心：

   • 使用一个 for 循环遍历字符串 s 的所有字符和字符之间的空隙作为回文中心，调用 expand_around_center 函数来检查并更新最长回文子串的 start 和 end。

5. 返回结果：

   • 返回 s[start:end + 1]，即最终找到的最长回文子串。

算法复杂度分析：

• 时间复杂度：O(n^2)。虽然是两重循环，但在每次迭代中的 expand_around_center 函数的操作只涉及线性的扩展，因此总体时间复杂度是可以接受的。
• 空间复杂度：O(1)。除了存储结果的 start 和 end 外，算法并没有使用额外的空间。

总结：

这种优化的中心扩展法是一种比较直观且有效的方法来寻找字符串中的最长回文子串。通过逐个字符和字符之间的空隙作为中心，向两边扩展并比较字符来确定回文子串的范围，最终找到整个字符串中的最长回文子串。