动态规划问题集

5. 最长回文子串

这题能在面试中做出来的有三种方法

1. 暴力 $O(n^3)$
2. 动态规划 $O(n^2)$
3. 中心扩展 $O(n^2)$

动态规划

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        ret = ''
        dp = [[0] * n for _ in range(n)]
        length = 1
        while length <= n:
            i = 0
            while i < n:
                j = i + length - 1
                if j >= n:
                    break
                if length == 1:
                    dp[i][j] = 1
                elif length == 2:
                    dp[i][j] = int(s[i] == s[j])
                else:
                    dp[i][j] = int(dp[i+1][j-1] and s[i] == s[j])
                if dp[i][j] and length > len(ret):
                    ret = s[i:j+1]
                i += 1
            length += 1
        return ret

状态定义:

dp[i][j]表示字符串从i到j，包括j，是否为回文字符串

状态转移方程：

$dp[i][j]= \begin{cases} 1 & dp[i+1][j-1] == 1\ and \ s[i]==s[j] \\ 0 & \ otherwise \end{cases}$

难点1：如何遍历dp二维数组比较恰当。这里我们用子字符串长度$length$来表示$j$, $j=i+length-1$, 由此我们可以实现二维数组对角线遍历而不会重复。

边界点1：$s$为空字符，我们在设置返回项时应该设置空字符（如果不提前规避的话）表示最长的回文字符串为空，长度为1。

边界点2：单字符，双字符，皆为该dp的边界点。我们应该首先计算出这些边界点的状态。可以在遍历大遍历之前小遍历初始化，也可以在整个遍历里设置单独条件计算这些边界点的状态。

边界点3：$j$越界，只要保证$j$不越界，那么$i+1$肯定也不越界。

中心扩展

其实个人觉得，比起dp，中心扩展法更少边界值，更容易上手。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        left, right = 0,0
        for i in range(len(s)):
            left1, right1 = self.centerExpand(s, i, i)
            left2, right2 = self.centerExpand(s, i, i+1)
            l, r = (left1, right1) if right1-left1 > right2-left2 else (left2, right2)
            left, right = (left, right) if right-left > r-l else (l, r)
        return s[left:right+1]

    def centerExpand(self, s, i, j):
        while 0 <= i and j < len(s) and s[i]==s[j]:
            i -= 1
            j += 1
        return i+1, j-1

中心扩展法其实就是利用边界点（单字符和双字符）去扩展得到所有的回文子串。

难点1：中心扩展函数的写法。一开始我用递归，有点麻烦，容易出错。后来看官方答案，这玩意要啥递归，while loop就完事了。

边界点：其实只要中心扩展函数写得好，基本不用考虑边界点。像上方官答，双字符是不相等和第二个字符越界的条件都不用考虑。