題目

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

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

示例 1：

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

示例 2：

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

思路1

從頭開(kāi)始遍歷字符串, 以遍歷到的字符為中心,向兩邊擴(kuò)散, 每擴(kuò)散一位,對(duì)比一下兩邊的值,直到不等時(shí) 記錄下 最長(zhǎng)的擴(kuò)散范圍,就是最長(zhǎng)的回文字串。

注意: 擴(kuò)散 起點(diǎn) 有2種情況,第一種 如 1 2 1, 此時(shí)一個(gè)中心; 第二種 1 2 2 1, 此時(shí)2個(gè)中心。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        res = ""
        for i in range(len(s)):
            # 1 2 1, 從同一元素開(kāi)始向兩邊
            tmp = self.helper(s, i, i)
            if len(tmp) > len(res):
                res = tmp
            
            # 2 1 1 2, 從挨著的2個(gè)元素開(kāi)始,向兩邊
            tmp = self.helper(s, i, i+1)
            if len(tmp) > len(res):
                res = tmp
        return res
    
    def helper(self, s, l, r):
        while l >= 0 and r <= len(s)-1 and s[l] == s[r]:
            l -= 1
            r += 1
        # while退出時(shí), l多減了1, r多加了1, 返回時(shí)需要補(bǔ)償回來(lái)
        return s[l+1: r]