Description:

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

5. 最長(zhǎng)回文子串

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

示例 1：

輸入: "babad"

輸出: "bab"

注意: "aba" 也是一個(gè)有效答案。

示例 2：

輸入: "cbbd"

輸出: "bb"

今天遇到最長(zhǎng)回文這道題，說實(shí)話對(duì)我來說是有點(diǎn)難度，攻了兩次才攻下來，個(gè)人覺得很有紀(jì)念意義，寫下來記錄一下。

Solution1: Greedy方法

回文字符串， 是正讀反讀都一樣的字符串。比較直接的方法是在每個(gè)字符位置上向前和向后搜索找到回文字符串。其中，對(duì)于搜索時(shí)需要對(duì)奇數(shù)位和偶數(shù)位兩種形式進(jìn)行探索，奇數(shù)位以當(dāng)前位置的字符為中心；偶數(shù)位以當(dāng)前位置和其相鄰一個(gè)位置的兩個(gè)字符為中心向兩邊拓展。

class Solution:
    def check_Palindrome(self,s,left,right):
        res =''
        while(left>=0 and right <len(s) and s[left] == s[right]):
            if len(res) < len(s[left:right+1]):
                res = s[left:right+1]
            left -= 1
            right += 1
        return res

    def longestPalindrome(self, s: str) -> str:
        l =len(s)
        res = ''
        for i in range(l):
            left = self.check_Palindrome(s,i,i)
            right = self.check_Palindrome(s,i,i+1)
            maxStr = None
            if(len(left)>len(right)):
                maxStr = left
            else:
                maxStr = right

            if(len(maxStr) > len(res)):
                res = maxStr
        return res