[数据结构与算法]动态规划之最长回文串

最长回文子串

leetcode 5

若一个字符串是回文串，那么它的首尾元素应该相同，并且若该字符串的长度大于2，除去首尾元素后依然是回文串。

由此可得到判断是否是回文串的递推公式，$P(i,j)$ 代表子串$S_i$到$S_j$是否是回文串：

$$P(i,j)=\{\begin{array}{ll}\text{?true,?}& \text{?如果子串?}{S}_i\dots S_j\text{?是回文串?}\\ \text{?false,?}& \text{?其它情况?}\end{array}$$

当且仅当$S_{i+1}$到$S_{j?1}$是回文串，即$P(i+1,j?1)=true$，且$S_i==S_j$时，$P(i,j)=true$

$$P(i,j)=P(i+1,j?1)\wedge \left(S_i==S_j\right)$$

对于所有是回文串的子串，记录其长度，选择最长的

代码如下：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # 字符串长度小于2，则整个字符串都是回文串
        n = len(s)
        if n < 2:
            return s
        
        begin = 0
        maxlen = 1  # 任意一个元素都是回文串
        
        # 初始化,dp[i][j]表示s[i]...s[j]的子串是否是回文串
        dp = [[False]*n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True
            # 任意一个元素s[i]都是回文串

        # 递推，遍历所有开始结束位置i,j。并判断是否是回文串
        for j in range(1,n):
            for i in range(j):
                if s[i] != s[j]:
                    # 首尾元素不相同，肯定不是回文串
                    dp[i][j] = False
                else:
                    if j-i < 3:
                        dp[i][j] = True
                        # 首尾元素相同，剩余部分少于一个元素
                    else:
                        dp[i][j] = dp[i+1][j-1]
                if dp[i][j] and j - i + 1 > maxlen:
                    # 记录最长的回文串索引
                    maxlen = j - i + 1
                    begin = i
        return s[begin:begin+maxlen]