最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

 

示例 1：

输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。
示例 2：

输入：s = “cbbd”
输出：”bb”

---

中心扩展法

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def helper(s, i, j):
            while i >= 0 and j < length and s[i] == s[j]:
                i = i - 1
                j += 1
            return i+1, j-1
        length = len(s)
        count = 0
        result = ""
        for i in range(length):
            left,right = helper(s, i, i+1)
            if right -left >= count:
                count = right - left
                result = s[left:right+1]
            # 这个地方比较巧妙
            left,right = helper(s, i, i)
            if right -left >= count:
                count = right - left
                result = s[left:right+1]
        return result

动态规划的方法

1.长度为1的串 必然为回文串
2.长度为2的串 如果字母相同也是回文串
3.如果s[i+1, j-1]是回文串且s[i]==s[j]则s[i, j]也是回文串

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:
            return s
        
        dp = [[False]*n for _ in range(n)]
        max_length = 1
        left = 0
        # L 表示子串长度
        for L in range(1, n+1):
            # i表示左index，j表示右index
            for i in range(n):
                j = L + i - 1
                # j非法时，退出循环
                if j > n - 1:
                    break
                if s[i] != s[j]:
                    dp[i][j] = False
                else:
                    if L <= 2:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i+1][j-1]
                if dp[i][j] and L > max_length:
                    max_length = L
                    left = i
        return s[left:left+max_length]

Manacher算法

TODO