【leetcode】#字元串【Python】5. Longest Palindromic Substring 最長回文子串

連結：

https://leetcode-cn.com/problems/longest-palindromic-substring/

題目：

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

示例 1：

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

示例 2：

輸入: “cbbd” 輸出: “bb”

解法1：周遊，每次從這個點往左往右判斷，能不能是對稱的

def longestPalindrome(self, s):
    res = ""
    for i in xrange(len(s)):
        # odd case, like "aba"
        tmp = self.helper(s, i, i)
        if len(tmp) > len(res):
            res = tmp
        # even case, like "abba"
        tmp = self.helper(s, i, i+1)
        if len(tmp) > len(res):
            res = tmp
    return res
 
# get the longest palindrome, l, r are the middle indexes   
# from inner to outer
def helper(self, s, l, r):
    while l >= 0 and r < len(s) and s[l] == s[r]:
        l -= 1; r += 1
    return s[l+1:r]
           

解法2: 先找到可能是字串的終點的點，比方[f a b c b a d]，先找第二個b，發現bcb是正反相同的，再找第二個a，判斷此時abcba是否相同 。比方[ f a b b a c]，先找到第二b，判斷bb是否正反相同，再判斷abba是否正反相同。耗時是解法1的約1/20。

class Solution(object):
    def longestPalindrome(self, s):
        if len(s)<2 or s==s[::-1]:
            return s
        n=len(s)
        start,max_len=0,1
        for i in range(1,n):
            odd=s[i-max_len-1:i+1]
            even=s[i-max_len:i+1]
            if i-max_len-1>=0 and odd==odd[::-1]:
                start=i-max_len-1
                max_len+=2
                continue
            if i-max_len>=0 and even==even[::-1]:
                start=i-max_len
                max_len+=1           
        return s[start:start+max_len]
           

解法3: 建一個二維矩陣相等的是1，不等的是0. 最後看右上到左下方向最長的連續1的所在字元串。