ericpuwang

最长回文串

https://leetcode.cn/problems/longest-palindromic-substring/description/

给你一个字符串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 not s:
            return ""

        start = 0
        max_len = 1
        for index in range(len(s)):
            # case1: 回文子串长度是奇数
            len1 = self.expand_from_center(s, index, index)
            # case2: 回文子串长度是偶数
            len2 = self.expand_from_center(s, index, index+1)
            cur_max_len = max(len1, len2)
            if cur_max_len > max_len:
                max_len = cur_max_len
                start = index - int((cur_max_len - 1)/2)
        return s[start:start+max_len]

    def expand_from_center(self, s: str, left: int, right: int) -> int:
        while (left >= 0 and right < len(s) and s[left] == s[right]):
            left -=1
            right += 1
        return right - left - 1