5. 最长回文子串

题目链接：国际版，国内版
公司：Meta

题目描述

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

思路

根据题意，给出一个字符串 s，想让我们找出 s 中的最长回文子串。题目包含两个信息：首先，回文串代表一个字符串正序和倒序是一样的；其次，子串代表是连续的字符不能跳跃。

对于求解这道题，我们可以用逆向思维来想一下，如果一个串是回文串则它有什么性质。由于回文串正序和倒序是一样的，因此它应该是一个对称的结构。也就意味着，我们去掉回文串的第一个和最后一个字符，剩下的字符串应该还是一个回文串，那么这也可以成为我们判断回文串的一个标准。如果我们以 dp[i][j] 代表子串s[i: j] 是否是回文串（布尔值），则状态转移方程为：

dp[i][j] = dp[i + 1][j - 1] and (s[i] == s[j])

这样一来，我们可以用动态规划的方式求解。假设 len(s) = N，那么我们需要构造一个 N * N 的矩阵，时间复杂度和空间复杂度都是 O(N^2)。该方法思路比较清晰且通用，但不算最优解。对于空间复杂度，我们还可以继续对其进行优化。

我们还可以换一种思路，那就是如何构造一个回文串。答案是：固定中间字符，向左右两侧扩散。当然了这里需要注意的一点是，这个中间字符可能是一个也可能是两个。当回文串长度为奇数时这个中间字符就只有一个，反之就有两个。因此，我们可以遍历 s 中的所有字符，并以当前字符作为中间字符（或当前字符与下一个字符一起作为中间字符）向左右扩散构建回文串，取最长的那一个，就是我们想要的答案。这种思路下，我们不需要申请额外的空间，空间复杂度降为 O(1)

该思路需要一个 helper function 用来进行回文串扩散。假设以 i 和 j 代表中间字符左右两侧的指针，则扩散的条件是 i，j 不越界且 s[i] == s[j]。

代码参考

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # T: O(N^2), S: O(1)
        def palindrome(s, i, j) -> str:
            """中心扩散寻找回文串"""
            while i >= 0 and j < len(s) and s[i] == s[j]:
                i -= 1
                j += 1
            return s[i + 1: j]
        
        res = ""
        for i in range(len(s)):
            s1 = palindrome(s, i, i)        # 长度为奇数的回文串
            s2 = palindrome(s, i, i + 1)    # 长度为偶数的回文串
            res = s1 if len(s1) > len(res) else res
            res = s2 if len(s2) > len(res) else res
        return res