leetcode5. 最長回文子串

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

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

示例 1：

輸入: “babad”

輸出: “bab”

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

示例 2：

輸入: “cbbd”

輸出: "bb"

首先想到的是暴力法，暴力枚舉所有子串O(n²),判斷是否為回文字元串O(n)，總的時間複雜度為O(n³),這種複雜度肯定不可取。

然後想到的動态規劃，因為如果i到j的子串是回文且i-1和j+1的字元是一樣的，那麼i-1到j+1的子串是回文。先算出長度為1 2的dp情況，再對長度為3到len(s)的情況依次求解，要注意不同長度時起始位置的範圍：

class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if not s:
            return ''
        max_length, start, length = 1, 0, 3
        dp = [[0]*len(s) for i in range(len(s))]
        for i in range(len(s)):
            dp[i][i] = 1  # 一個字元始終是回文
            if i < len((s))-1 and s[i] == s[i+1]:
                dp[i][i+1] = 1
                start = i
                max_length = 2
        for length in range(3, len(s)+1):
            for i in range(len(s)-length+1):
                j = i + length - 1
                if dp[i+1][j-1] and s[i] == s[j]:
                    dp[i][j] = 1
                    start = i
                    max_length = length
        return s[start:start+max_length]
           

上面動态規劃把時間複雜度降到了O(n²)，但也有O(n²)的空間複雜度。對于一個回文子串，如果左右兩邊相等，那麼再加上左右兩邊的結果也是回文子串，這讓我們想到了可以從中心來拓展子串。子串的中心可以為1個或者兩個，是以一共有2n-1個中心，然後依次從第一個字元開始中心拓展，找到最長的子串。這樣的做法空間複雜度為O(1)。

class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if not s:
            return ''
        start, end = 0, 0
        for i in range(len(s)):
            len1 = self.expand(s, i, i)  # 奇數
            len2 = self.expand(s, i, i+1)  # 偶數
            length = max(len1, len2)
            if length > end-start:
                start = i - (length-1) // 2
                end = i + (length) // 2
        return s[start:end+1]

    def expand(self, s, left, right):
        while left >=0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return right-left-1  # 傳回長度
           

Manacher算法看這裡。