【Leetcode】【python】Longest Palindromic Substring 最长回文子串

题目大意

给出一个字符串S，找到一个最长的连续回文串。

解题思路

经典讲解参考：

https://www.cnblogs.com/bitzhuwei/p/Longest-Palindromic-Substring-Par-I.html#_labelTop

暴力穷举法O(N3)
显然有C(N,2)（组合）个子串。检测每个子串都需要O(N)的时间，所以此方法的时间复杂度为O(N3)。

动态规划O(N2)时间O(N2)空间
定义二维数组P[i,j]用以表示Si…Sj是回文（true）或不是回文（false）

那么可知状态转移方程：P[i,j] = (P[i + 1, j - 1] && Si ==Sj)

初始条件是：P[i, i] = true，P[i, i + 1] = (Si == Si+1)

这个DP法的思路就是，首先可以知道单个字符和两个相邻字符是否回文，然后检测连续三个字符是否回文，然后四个。

此算法时间复杂度O(N2)，空间复杂度O(N2)。

注意：
1.判断空字符串
2.这题遍历切不可横向遍历，否则例如abcba，是无法先将bcb置为1的，进而无法将abcba置为1。
应该如图所示，向右下方先遍历。(后来想想，从下面开始横向遍历也是可以的，只是不可从上面)

class Solution(object):
    
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if not s:
            return ''
        # 先将任一单个字母作为结果
        start = 0
        maxlen = 1
        dp = [[0 for __ in range(len(s))] for __ in range(len(s))]
        # 将长度1和长度2（相同字母）情况初始化赋值
        for i in range(len(s)):
            dp[i][i] = 1
            if (i < len(s) - 1) and (s[i] == s[i+1]):
                dp[i][i+1] = 1
                start = i
                maxlen = 2
        # for line in dp:
        #     print line
        # 注意：不可横向遍历，否则例如abcba，是无法先将bcb置为1的，进而无法将abcba置为1
        # 从长度3开始
        for length in range(3, len(s)+1):
            for i in range(len(s)-length+1):
                j = i + length - 1
                if (dp[i+1][j-1] == 1) and s[i] == s[j]:
                    dp[i][j] = 1
                    if length > maxlen:
                        start = i
                        maxlen = length
        # for line in dp:
        #     print line
        return s[start:start+maxlen]

中心检测法

下面介绍一个O(N2)时间O(1)空间的算法。

回文的特点，就是中心对称。对于有N个字符的字符串S，只有2N-1个中心。

为何是2N-1？因为两个字符之间的空档也可以是一个中心。例如”abba”的两个b中间就是一个中心。

围绕一个中心检测回文需要O(N)时间，所以总的时间复杂度是O(N2)。

class Solution(object):
    
    def getlongestpalindrome(self, s, l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1; r += 1
        return s[l+1 : r]  # 例如bab，最后l=-1，r=3，所以要s[l+1 : r]也就是[0,3] 
    
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        palindrome = ''
        for i in range(len(s)):
            len1 = len(self.getlongestpalindrome(s, i, i))  # len1是中间是单一字母的回文数
            if len1 > len(palindrome): 
                palindrome = self.getlongestpalindrome(s, i, i)
            len2 = len(self.getlongestpalindrome(s, i, i + 1))  # len2是中间是和后面一个字母相同的回文数
            if len2 > len(palindrome): 
                palindrome = self.getlongestpalindrome(s, i, i + 1)
        return palindrome

总结

• 回文有两种可能：aba和abba

• 此题动态规划通过效率不高，不如中心检测法