LeetCode5:最长回文子串

题目

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

输入：s = "cbbd"
输出："bb"

• 1 <= s.length <= 1000

• s 仅由数字和英文字母组成

解析

1. 动态规划

class Solution:
    def longestPalindrome(self, s: str) -> str:
        dp = [[False] * len(s) for _ in s]

        left, right = 0, 0
        for i in range(len(dp)-1, -1, -1):
            for j in range(i, len(dp)):
                if i == j:
                    dp[i][j] = True
                elif i == j - 1:
                    dp[i][j] = s[i] == s[j]
                else:
                    dp[i][j] = s[i] == s[j] and dp[i+1][j-1]
                if dp[i][j] and right - left < j - i:
                    left, right = i, j
        return s[left:right+1]

1. 中心扩展法

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n, m = 0, 0
        for i in range(len(s)):
            left, right = i, i
            while left >= 0 and s[left] == s[i]: left -= 1
            while right < len(s) and s[right] == s[i]: right += 1
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            if m - n + 1 < right - left - 1:
                n, m = left + 1, right - 1
        rMan

1. Manacher算法（马拉车算法）

力扣

https://leetcode-cn.com/problems/longest-palindromic-substring/solution/tu-jie-ma-la-che-suan-fa-by-wang_ni_ma-if33/