題目鏈接

難度：中等 ??????類型： 字符串

給定一個字符串 s，找到 s 中最長的回文子串。你可以假設(shè) s 的最大長度為 1000。

示例1

輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個有效答案。

示例2

輸入: "cbbd"
輸出: "bb"

解題思路

遍歷字符串，以每個字符和以每相鄰兩字符作為中心，搜索以其為中心的回文串長度，保存當(dāng)前最長回文子串

中心擴(kuò)展法判斷是否符合回文要求

代碼實現(xiàn)

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        def expand(s, left, right):
            
            while left>=0 and right<len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return right-left-1
        start = 0
        end = 0
        for i in range(len(s)):
            len1 = expand(s, i, i)
            len2 = expand(s, i, i+1)
            max_len = max(len1, len2)
           
            if max_len > end - start:
                start = i - (max_len-1)/2
                
                end = i + max_len/2
        return s[start:end+1]

本文鏈接：http://www.itdecent.cn/p/faa70571e3d3