Jianbo Dai's

lc005.最长回文子串

 
  • Jan 29, 2021

题目链接

暴力算法就不说了时间复杂度是O（N^3），写一个时间复杂度稍微优一点的算法吧，就是用二维的动态规划。思路如下。对于一个子串而言，如果它是回文串，并且长度大于2，那么将它首尾的两个字母去除之后，它仍然是个回文串。例如对于字符串“ababa”，如果我们已经知道“bab”是回文串，这是因为它的首位两个字母都是“a”。我们用P（i，j）表示字符串s的第i到第j个字母组成的串（下文表示成s[[i:j]）是否为回文串：如果它的子串Si…Sj为回文串，那么P（i，j）是回文串，除非当发生i>j或者s[i,j]本身不是一个回文串的情况。那我们可以写出状态转移方程: P(i,j) = P(i+1,j-1) and (Si == Sj)，也就是说只有s[i+1;j-1]是回文串且s的第i，j个字母相同时s[i:j]才会是回文串。当然上文的所有讨论是建立在子串长度大于2的前提之上的，我们还需要考虑动态规划中的边界条件，即子串的长度为1或2。对于长度为1的子串，显然是个回文串；对于长度为2的子串，只要它的两个字母相同，它就是一个回文串。根据这个思路，我们就可以完成动态规划了，最终的答案即为所有P(i,j) = true中j-i+1（即子串长度）的最大值。这个算法的时间复杂度是O（N^2），空间复杂度是O（N^2）。

python:

class Solution:
    def longestPalindrome(self, s: str) -> str:
        size = len(s)
        dp = [[False]*size for _ in range(size)]

        for i in range(size):
            dp[i][i] = True
        
        maxLen = 1
        begin = 0
        for i in range(size-1, -1, -1):
            for j in range(i+1, size):
                if s[i] == s[j]:
                    if j - i < 3 or dp[i+1][j-1]:
                        dp[i][j] = True
                else:
                    dp[i][j] = False

                if dp[i][j] and j - i + 1 > maxLen:
                    maxLen = j - i + 1
                    begin = i
        
        return s[begin:begin+maxLen]
Search