返回输入字符串的最长回文子串

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

示例 1：

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

输入: "cbbd"
输出: "bb"

 

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        len_str = len(s)
        if len(s) == 0:
            return ""
        if len(s) == 1:
            return s
        # 考虑最长子串的长度是奇数还是偶数

        even_len, even_str = [], []
        odd_len,  odd_str = [], []

        # 奇数
        for i in range(len_str):
            left, right = i, i
            while left >= 0 and right < len_str and s[left] == s[right]:
                left -= 1
                right += 1
                odd_len.append(right-left-1)  # len
                odd_str.append(s[left+1:right])  # str
                

        # 偶数
        for i in range(len_str):
            left, right = i, i+1
            while left >= 0 and right < len_str and s[left] == s[right]:
                left -= 1
                right += 1
                even_len.append(right-left-1)  # len
                even_str.append(s[left+1:right])  # str
        return max((even_str+odd_str), key=lambda x: len(x))


if __name__ == "__main__":
    ss = Solution()
    print(ss.longestPalindrome("babad"))