LeetCode 第 5 题：最长回文子串

LeetCode 第 5 题：最长回文子串

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例

示例 1：

输入："babad"
输出："bab"
注意："aba" 也是一个有效答案。

示例 2：

输入："cbbd"
输出："bb"

题目解析

看到该题目，首先想到的是遍历字符串，取出子串，判断其逆置后是否与其相同，即判断是否符合回文。从中寻找最长的一个。这是暴力破解法。

暴力破解法

class Solution:
    def longestPalindrome(self, s: str) -> str:
        string = ""
        length = -1
        for i in range(len(s)):
            for j in range(i, len(s)):
                a = s[i:j+1]
                if a == a[::-1] and len(a) > length:
                    string = a
                    length = len(a)
        return string

其中 a[::-1] 运用了列表的切片，使其逆序排列。执行测试数据时通过了，但在提交的时候出了问题，原因是超时。因为该方法需要两层循环，对于长字符串（如'一千个一'）会导致超时。

中心扩展算法

参考题解后，采用中心扩展算法。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if s == s[::-1]:
            return s
        res = s[:1]
        for i in range(len(s)):
            len1 = self.expandAroundCenter(s, i, i)
            len2 = self.expandAroundCenter(s, i, i+1)
            res = max(res, len1, len2, key=len)
        return res
    
    def expandAroundCenter(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left+1:right]

中心扩展算法需要考虑 2N+1 个中心。分别为回文子串长度为奇数时，中心值为中间一个字符；回文子串长度为偶数时，中心值为中间两个字符。循环遍历这些情况，再建立一个从中间扩展两侧字符的函数，当两侧字符一致时，向外扩展一层。