5. 最长回文子串

5. 最长回文子串

题目

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

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

示例 2：

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

示例 3：

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

示例 4：

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

题解

动态规划

用 i, j 分别表示左右指针，用 f(i,j) 判断 s[i:j+1] 是否为回文串，那么

再加上记忆化搜索记录状态即可，时间复杂度为

from functools import lru_cache
class Solution:
    def longestPalindrome(self, s: str) -> str:
        @lru_cache(maxsize=None)
        def f(i, j):
            if i == j:
                return True
            elif i > j:
                return True
            elif s[i] != s[j]:
                return False
            else:
                return f(i+1, j-1)
        max_len = -1
        for i in range(len(s)):
            for j in range(len(s)-1, i-1, -1):
                if f(i, j) and j-i+1 > max_len:
                    max_len = j-i+1
                    left, right = i, j
        return s[left:right+1]

方法很优美，很可惜直接超时了。。。

贪心

由于所有的回文串都会有一个中心，所以我们只需找出这个中心即可：

1. 我们先确定一个中心位置 k
   1. 以 k 为中心扩张，找出最大奇数长度回文串
   2. 以 k,k+1 为中心扩张，找出最大偶数长度回文串
2. 将 k 遍历所有位置

   class Solution:
    def longestPalindrome(self, s: str) -> str:
        i, j, n = 0, 0, len(s)
        max_len = -1
        max_str=s[0]
        for k in range(0, n-1):
            i, j = k-1, k+1
            while i >= 0 and j < n and s[i] == s[j]:
                if j-i+1 > max_len:
                    max_len = j-i+1
                    max_str = s[i:j+1]
                i -= 1
                j += 1
            i, j = k, k+1
            while i >= 0 and j < n and s[i] == s[j]:
                if j-i+1 > max_len:
                    max_len = j-i+1
                    max_str = s[i:j+1]
                i -= 1
                j += 1
        return max_str
   

   执行用时：704 ms, 在所有 Python 提交中击败了83.39%的用户 内存消耗：13.2 MB, 在所有 Python 提交中击败了61.35%的用户

该方法时间复杂度为 ，其中m为最长回文串的长度