LeetCode 5. Longest Palindromic Substring 最长回文子串 Python 四种解法(Manacher 动态规划)

Longest Palindromic Substring 最长回文子串 学习笔记

1. Brute method

第一种方法：直接循环求解，$o(n^2)$

class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        l = len(s)
        max_length = 0
        palindromic = ''
        if len(s) == 1:
            return s
        for i in range(l):
            for j in range(i + 1, l):
                is_palindromic = True
                for k in range(i, int((i + j) / 2) + 1):
                    if s[k] != s[j - k + i]:
                        is_palindromic = False
                        break
                if is_palindromic and (j - i + 1) > max_length:
                    max_length = j - i + 1
                    palindromic = s[i:j + 1]
        if palindromic == '':
            palindromic = s[0]
        return palindromic

2. 中心枚举

通过枚举字符串子串的中心而不是起点，向两边同时扩散，依然是逐一判断子串的回文性。这种优化算法比之前第一种算法在最坏的情况下（即只有一种字符的字符串）效率会有很大程度的上升。

class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        l = len(s)
        max_length = 0
        palindromic = ''
        for i in range(l):
            x = 1
            while (i - x) >= 0 and (i + x) < l:
                if s[i + x] == s[i - x]:
                    x += 1
                else:
                    break
            x -= 1
            if 2 * x + 1 > max_length:
                max_length = 2 * x + 1
                palindromic = s[i - x:i + x + 1]
            x = 0
            if (i + 1) < l:
                while (i - x) >= 0 and (i + 1 + x) < l:
                    if s[i + 1 + x] == s[i - x]:
                        x += 1
                    else:
                        break
            x -= 1
            if 2 * x + 2 > max_length:
                max_length = 2 * x + 2
                palindromic = s[i - x:i + x + 2]
        if palindromic == '':
            palindromic = s[0]
        return palindromic

3. Manacher’s Algorithm

复杂度$o(n)$
有两个主要的步骤:

1. 将所有可能的奇数/偶数长度的回文子串都转换成了奇数长度：在每个字符的两边都插入一个特殊的符号。abba => #a#b#b#a#， aba => #a#b#a#
2. 用数组 P[i] 来记录以字符S[i]为中心的最长回文子串向左/右扩张的长度，并增加两个辅助变量id和mx，其中 id 为已知的 {右边界最大} 的回文子串的中心，mx则为id+P[id]，也就是这个子串的右边界。
   $mx-i>p[j]:p[i]=p[j]$
   $mx-i<=p[j]:p[i]=mx-i$

# manacher算法
def manacher(self):
        s = '#' + '#'.join(self.string) + '#'               # 字符串处理，用特殊字符隔离字符串，方便处理偶数子串
        lens = len(s)
        f = []                                          # 辅助列表：f[i]表示i作中心的最长回文子串的长度
        maxj = 0                                        # 记录对i右边影响最大的字符位置j
        maxl = 0                                        # 记录j影响范围的右边界
        maxd = 0                                        # 记录最长的回文子串长度
        for i in range(lens):                           # 遍历字符串
            if maxl > i:
                count = min(maxl-i, int(f[2*maxj-i]/2)+1)  # 这里为了方便后续计算使用count，其表示当前字符到其影响范围的右边界的距离
            else :
                count = 1
            while i-count >= 0 and i+count < lens and s[i-count] == s[i+count]:  # 两边扩展
                count += 1
            if(i-1+count) > maxl:                         # 更新影响范围最大的字符j及其右边界
                maxl, maxj = i-1+count, i
            f.append(count*2-1)
            maxd = max(maxd, f[i])                       # 更新回文子串最长长度
        return int((maxd+1)/2)-1                        # 去除特殊字符

4. 动态规划

基本思路是对任意字符串，如果头和尾相同，那么它的最长回文子串一定是去头去尾之后的部分的最长回文子串加上头和尾。如果头和尾不同，那么它的最长回文子串是去头的部分的最长回文子串和去尾的部分的最长回文子串的较长的那一个。
$P[i,j]$表示第i到第j个字符的回文子串数
$dp[i,i]=1$
$dp[i,j]=dp[i+1,j-1]+2|s[i]=s[j]$
$dp[i,j]=max(dp[i+1,j],dp[i,j-1])|s[i]!=s[j]$

   def longestPalindrome(s):
        n = len(s)
        maxl = 0
        start = 0
        for i in xrange(n):
            if i - maxl >= 1 and s[i-maxl-1: i+1] == s[i-maxl-1: i+1][::-1]:
                start = i - maxl - 1
                maxl += 2
                continue
            if i - maxl >= 0 and s[i-maxl: i+1] == s[i-maxl: i+1][::-1]:
                start = i - maxl
                maxl += 1
        return s[start: start + maxl]

5. Discuss看到的一个解法

while k < lenS - 1 and s[k] == s[k + 1]: k += 1 is very efficient and can handle both odd-length (abbba) and even-length (abbbba).

def longestPalindrome(self, s):
    lenS = len(s)
    if lenS <= 1: return s
    minStart, maxLen, i = 0, 1, 0
    while i < lenS:
        if lenS - i <= maxLen / 2: break
        j, k = i, i
        while k < lenS - 1 and s[k] == s[k + 1]: k += 1
        i = k + 1
        while k < lenS - 1 and j and s[k + 1] == s[j - 1]:  k, j = k + 1, j - 1
        if k - j + 1 > maxLen: minStart, maxLen = j, k - j + 1
    return s[minStart: minStart + maxLen]

参考文献

1. https://www.felix021.com/blog/read.php?2040
2. http://blog.csdn.net/backkom_lory/article/details/53896664
3. https://leetcode.com/problems/longest-palindromic-substring/discuss/3190/