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算法看这里。