最长回文子串动态规划

回文串（palindrome）是指从左往右读和从右往做读都一样的字符串。例如，”aba”、”abba”、”babad”都是回文串。

最长回文子串（Longest Palindromic Substring，简称LPS）指的是给定一个字符串，找到其中最长的回文子串。

解法分析

最直接的想法是枚举所有子串并验证是否为回文串，但这个方法会超时，时间复杂度为$O(n^3)$。

更优秀的解法是基于动态规划算法实现，时间复杂度为$O(n^2)$。

我们用$P(i,j)$表示$i$到$j$中是否为回文串，$P(i,j)$的定义如下：

P(i,j)=true   [i,j]为回文串
P(i,j)=false  [i,j]不是回文串

当$i=j$时，$P(i,j)=true$;
当$j=i+1$时，$P(i,j)$要看$i$和$j$是否相等；
当$j>i+1$时，$P(i,j)$要看$P(i+1,j-1)$是否为回文串，以及$i$和$j$是否相等。

我们考虑用“填表法”来解决这个问题，创建一个二维表格$dp$，从左上角开始遍历，从而把所有可能情况的$P(i,j)$都计算出来。初始化时，所有的$dp[i][i]$的值均为$true$，因为单个字符是回文串。

填表示例如下所示：

最后，在得到表格后，我们可以通过遍历所有的$dp[i][j]$，找到最长的为true的$i,j$，并返回这个最长回文子串。

代码实现

代码如下所示：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        ans = ""
        for l in range(n):
            for i in range(n):
                j = i + l
                if j >= n:
                    break
                if l == 0:
                    dp[i][j] = True
                elif l == 1:
                    dp[i][j] = (s[i] == s[j])
                else:
                    dp[i][j] = (dp[i+1][j-1] and s[i] == s[j])
                if dp[i][j] and l + 1 > len(ans):
                    ans = s[i:j+1]
        return ans

总结

本文介绍了求解最长回文子串问题的一个基于动态规划的解法，时间复杂度为$O(n^2)$。在具体实现中，我们采用“填表法”来求解。

如果你还有问题，欢迎留言交流。