5. 最长回文子串

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

示例 1：

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

输入: “cbbd” 输出: “bb”

暴力

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        size = len(s)
        if size < 1:
            return s

        max_len = 1
        res = s[0]

        for i in range(size-1):
            for j in range(i+1, size):
                if  j - i + 1  > max_len and self.is_valid(s, i, j):
                    max_len =  j - i + 1
                    res = s[i:j+1]
        return res

    def is_valid(self, s, left, right):
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        size = len(s)
        if size < 1:
            return s

        max_len = 1
        res = s[0]

        for i in range(size):
            odd, odd_len = self.spread_from_center(s, i, i)
            even, even_len = self.spread_from_center(s, i, i+1)
            max_sub = odd if odd_len > even_len else even
            if len(max_sub) > max_len:
                max_len = len(max_sub)
                res = max_sub
        return res

    def spread_from_center(self, s, left, right):
        if not s or left > right:
            return '', 0
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left+1:right], right - left - 1