题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：

输入: "cbbd"
输出: "bb"

思路：

• Manacher算法
• 中心扩散
  中心扩散法的想法很简单：遍历每一个索引，以这个索引为中心，利用“回文串”中心对称的特点，往两边扩散，看最多能扩散多远。要注意一个细节：回文串的长度可能是奇数，也可能是偶数。
  我们完全可以设计一个方法，兼容以上两种情况：
  1、如果传入重合的索引编码，进行中心扩散，此时得到的最长回文子串的长度是奇数；
  2、如果传入相邻的索引编码，进行中心扩散，此时得到的最长回文子串的长度是偶数。
• 动态规划
  1.动态数组记录是否是回文，然后计算长度。dp[j][i]表示是s[j:i+1]是否是回文
  2.如果满足s[j]和s[i]相等，如果，dp[j+1][i-1]是，dp[j][i]也是回文。

class Solution:
    def longestPalindrome(self, s):
        if not s or len(s) == 0:
            return ""
        ans = ""
        for i in range(len(s)):
            ans = self.helper(s, i, i, ans)
            ans = self.helper(s, i, i + 1, ans)
        return ans

    def helper(self, s, left, right, ans):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
            if (right - left - 1) > len(ans):
                ans = s[left+1:right]
        return ans

AC5中心扩散

class Solution1:
    def longestPalindrome(self, s):
        if not s:
            return ""
        n = len(s)
        # 动态数组记录是否是回文，然后计算长度
        dp = [[0] * n for _ in range(n)]
        max_len = float("-inf")
        for i in range(n):
            for j in range(i+1):
                # 如果满足s[j]和s[i]相等，如果，dp[j+1][i-1]是，dp[j][i]也是回文
                # 还有3种情况，概括为 i - j <= 2.代表j到i中只有一个元素，没有元素，i == j，都是直接成立的
                if s[i] == s[j] and (i - j <= 2 or dp[j+1][i-1]):
                    dp[j][i] = 1
                if dp[j][i] == 1 and (i - j + 1) > max_len:
                    max_len = i + 1 - j
                    res = s[j:i+1]
        return res

AC5动态规划