Python 求解--最长回文子串

用户4945346

发布于 2024-04-30 19:46:54

730

发布于 2024-04-30 19:46:54

文章被收录于专栏：pythonista的日常pythonista的日常

这是力扣第五题，根据给定的一个字符串 s，找到 s 中最长的回文子串。如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。回文数字长度可以是奇数个也可以是偶数个。

示例 1：

输入：s = "babad" 输出："bab"

解释："aba" 同样是符合题意的答案。

示例 2：

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

解题思路：

使用中心扩散法遍历每个元素,判断其左右两侧是否对称(即是否为回文)。需考虑回文长度为奇数和偶数两种情况。如果较大的父字符串是回文,其子串也一定是回文。记录下每个回文子串的起始和结束位置,注意处理边界情况。最后根据这些位置获取并输出所有回文子串。

代码如下:

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""

        n = len(s)
        start, max_length = 0, 0

        for i in range(n):
            # 以当前字符为中心的奇数长度回文子串，b-->cbc-->acbca
            left, right = i, i
            # 判断是否为回文
            while left >= 0 and right < n and s[left] == s[right]:
                # 如果长度 > max_length 则更新 max_length
                if right - left + 1 > max_length:
                    start = left
                    max_length = right - left + 1
                left -= 1
                right += 1

            # 以当前字符和下一个字符之间为中心的偶数长度回文子串 bb-->cbbc-->acbbca
            left, right = i, i + 1
            while left >= 0 and right < n and s[left] == s[right]:
                if right - left + 1 > max_length:
                    start = left
                    max_length = right - left + 1
                left -= 1
                right += 1

        return s[start:start + max_length]