leetcode 5. 最长回文子串

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

示例 1：

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

输入：s = "cbbd"
输出："bb"
示例 3：

输入：s = "a"
输出："a"
示例 4：

输入：s = "ac"
输出："a"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

DP动态规划，

计算方法（DP）：

　　遍历i-j间隔，从1开始，到l-1

　　如果s[i:j+1]是回文的话，需要满足两个条件，s[i+1:j]是回文串，并且s[i]等于s[j+1]。

题解：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        l = len(s)
        flag = [[True] * l for i in range(l)]
        rlen = 0
        rstr = ''
        for i in range(0, l):
            for j in range(l - i):
                flag[j][j + i] = (flag[j + 1][j + i - 1] and s[j] == s[j + i]) if i else True
                if (flag[j][j + i] and i + 1 > rlen):
                    rlen = i + 1
                    rstr = s[j:j + i + 1]
        return rstr
print(Solution.longestPalindrome(Solution,'a'))

注意：一般情况，面试手敲的话不会要求使用$\text{Manacher马拉车算法，但是需要知道它的存在，了解它的原理（比赛一般直接上模板）。}$