leetcode-5

5. 最长回文子串

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

示例

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

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

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

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

官方题解

方法一：动态规划

对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串。例如对于字符串 “ababa”，如果我们已经知道 “bab”是回文串，那么 “ababa”一定是回文串，这是因为它的首尾两个字母都是“a”。

根据这样的思路，我们就可以用动态规划的方法解决本题。用$P(i,j)$表示字符串$s$的第$i$到$j$个字母组成的串（下文表示成$s[i:j]$）是否为回文串：
$$
P(i, j)=\left{\begin{array}{l}
\text { true, } &如果子串S_i\dots S_j是回文串 \
\text { false, } &其它情况
\end{array}\right.
$$

这里的其他情况包含两种可能性：

• $s[i,j]$ 本身不是一个回文串
• $i>j$，此时$s[i,j]$本身不合法

那么我们就可以写出动态规划的状态转移方程：
$$
P ( i , j ) = P ( i + 1 , j - 1 ) \wedge \left( S _ { i } = = S _ { j } \right)
$$
也就是说，只有$s [ i + 1 : j - 1 ]$是回文串，并且$s$的第$i$和$j$个字母都相同时，$s[i:j]$才会是回文串。

这里对应前面的描述

上文的所有讨论是建立在子串长度大于 2 的前提之上的，我们还需要考虑动态规划中的边界条件，即子串的长度为 1 或 2。

对于长度为 1 的子串，它显然是个回文串；对于长度为 2 的子串，只要它的两个字母相同，它就是一个回文串。因此我们就可以写出动态规划的边界条件：
$$
\left{
\begin{array} { l } P (i , i ) = \text { true } \
P (i , i + 1 ) = \left(S _{ i } = = S _{ i + 1 } \right)
\end{array} \right.
$$
根据这个思路，我们就可以完成动态规划了，最终的答案即为所有$P ( i , j ) =\text{true}$中$j-i+1$（即子串长度）的最大值。

注意：在状态转移方程中，我们是从长度较短的字符串向长度较长的字符串进行转移的，因此一定要注意动态规划的循环顺序。

方法二：中心扩展算法

仔细观察一下方法一中的状态转移方程：
$$
\left{
\begin{array} {ll} P (i , i ) & = \text { true } \ P (i , i + 1 ) & = \left(S _{ i } = = S _{ i + 1 } \right) \ P (i , j ) & = P (i + 1 , j -1 ) \wedge \left(S _{ i } = = S _{ j } \right)
\end{array}
\right.
$$
找出其中的状态转移链：
$$
P ( i , j ) \leftarrow P ( i + 1 , j - 1 ) \leftarrow P ( i + 2 , j - 2 ) \leftarrow \cdots \leftarrow \text{某一边界情况}
$$
可以发现，所有的状态在转移的时候的可能性都是唯一的。也就是说，我们可以从每一种边界情况开始「扩展」，也可以得出所有的状态对应的答案。

边界情况即为子串长度为 1 或 2 的情况。我们枚举每一种边界情况，并从对应的子串开始不断地向两边扩展。

如果两边的字母相同，我们就可以继续扩展，例如从$P ( i + 1 , j - 1 )$扩展到$P(i,j)$；

如果两边的字母不同，我们就可以停止扩展，因为在这之后的子串都不能是回文串了。

聪明的读者此时应该可以发现，「边界情况」对应的子串实际上就是我们「扩展」出的回文串的「回文中心」。

方法二的本质即为：我们枚举所有的「回文中心」并尝试「扩展」，直到无法扩展为止，此时的回文串长度即为此「回文中心」下的最长回文串长度。我们对所有的长度求出最大值，即可得到最终的答案。

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) # 边界情况，长度为1的子串
            left2, right2 = self.expandAroundCenter(s, i, i + 1) # 边界情况，长度为2的子串
            if right1 - left1 > end - start:
                start, end = left1, right1
            if right2 - left2 > end - start:
                start, end = left2, right2
        return s[start: end + 1]