5_最长回文子串

类型：字符串

最长回文子串 💛

https://leetcode-cn.com/problems/longest-palindromic-substring/

❓ 找到字符串 s 中的最长回文子串。

💡 动态规划

单个字符属于回文串。双字符如果相等的话，也属于回文串。

另外，对于一个长度大于 2 的回文串来说，将它的首尾去掉后，剩下的部分仍然是回文串。

dp[i][j] 表示子串 [i, j] 是否为回文串（True / False）。

转移方程：dp[i][j] = dp[i + 1][j - 1] and s[i] == s[j]

通过转移方程可以看出，长串的 dp 是依赖于短串的。因此我们通过串长度从小到大，先更新短串的 dp，再更新长串的 dp。先枚举串长度，再枚举串起点，串终点可以计算得来。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""
        n = len(s)
        start = end = 0
        dp = [[False] * n for _ in range(n)]
        for length in range(1, n + 1):
            for i in range(n):
                j = i + length - 1
                if j >= n:
                    break
                if length == 1:
                    dp[i][j] = True
                elif length == 2:
                    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 j - i > end - start:
                    start, end = i, j
        return s[start: end + 1]

时间复杂度：O(n^2)，空间复杂度：O(n^2)

💡 中心扩展法

枚举回文子串的中心，向两边扩展。注意，子串中心可能是一个字符（如 aba），也可能是两个字符（如 abba）。

class Solution:
    def expandAroundCenter(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1

    def longestPalindrome(self, s: str) -> str:
        start, end = 0, 0
        for i in range(len(s)):
            left1, right1 = self.expandAroundCenter(s, i, i)
            left2, right2 = self.expandAroundCenter(s, i, i + 1)
            if right1 - left1 > end - start:
                start, end = left1, right1
            if right2 - left2 > end - start:
                start, end = left2, right2
        return s[start: end + 1]

时间复杂度：O(n^2)，空间复杂度：O(1)

💡 Manacher 算法

比较复杂，面试中一般不要求。可以作为发挥亮点。参见官方题解。

时间复杂度：O(n)，空间复杂度：O(n)