Longest Palindromic Substring

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. 最長回文子串

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

示例 1：

輸入: "babad"

輸出: "bab"

注意: "aba" 也是一個有效答案。

示例 2：

輸入: "cbbd"

輸出: "bb"

今天遇到最長回文這道題，說實話對我來說是有點難度，攻了兩次才攻下來，個人覺得很有紀念意義，寫下來記錄一下。

Solution1: Greedy方法

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

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