Topic

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

Example_1

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

Example_2

输入：s = “cbbd”
输出：“bb”

Example_3

输入：s = “a”
输出：“a”

Example_4

输入：s = “ac”
输出：“a”

Tips

1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成

Solution

本题可以采用中心拓展法来解决

综合本题其实可分为两种情况：

回文为奇数：例如“abcba”
回文为偶数：例如“abba”

那么区分这两种情况的办法如下：

奇数回文，初始化left == right
偶数回文，初始化right == left + 1

之后我们可以设计一个函数find用来判断是否满足回文
find函数判断时需同时满足如下条件即为回文：

left >= 0
right < len(s)
s[left] == s[right]

最后返回奇数及偶数回文两种判断结果的最后结果
即为所求

Code

class Solution:
    def longestPalindrome(self, s):
        n = len(s)  # 排除s为空或者回文是s自己
        if n < 2:
            return s
        res = ''
        def find(left, right,res):
            while left >= 0 and right < n and s[left] == s[right]:
                left -= 1
                right += 1
            return s[left + 1: right] if right - left - 1 > len(res) else res

        for i in range(n):
            res = find(i, i, res)
            res = find(i, i + 1, res)
        return res

Res