Skip to content

005 longest palindromic substring

5. Longest Palindromic Substring

题目:

https://leetcode.com/problems/longest-palindromic-substring/

难度:

Medium

思路0:

暴力解法绝对不行

思路1:

所以一个好的想法是 s 和 reverse(s) 共有的最长的 substring就是longest palindromic substring -> 问题转成求Longest common substring problem

参见wikipedia

,典型动归

LCSuff(S1...p, T1...q) = LCS(S1...p1, T1...q-1) if S[p] = T[q] else 0

伪码也有了,代码也有:

https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_substring#Python_2

这样也超时?

    class Solution(object):
        def longestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            """
            def lcs(s1, s2):
                m = [[0] * (1 + len(s2)) for i in xrange(1 + len(s1))]
                longest, x_longest = 0, 0
                for x in xrange(1, 1 + len(s1)):
                    for y in xrange(1, 1 + len(s2)):
                        if s1[x - 1] == s2[y - 1]:
                            m[x][y] = m[x - 1][y - 1] + 1
                            if m[x][y] > longest:
                                longest = m[x][y]
                                x_longest = x
                        else:
                            m[x][y] = 0
                return s1[x_longest - longest: x_longest]

            return lcs(s, s[::-1])

因为以为这样s[::-1]已经很快了.

这个方法是buggy的,看字符串abcxgcba,它reverse之后是abcgxcba,它们有公共字符串,但是这里面没有回文,修复方式是:

we check if the substring’s indices are the same as the reversed substring’s original indices. If it is, then we attempt to update the longest palindrome found so far; if not, we skip this and find the next candidate.

我觉得的修复方式这样么:

原本     翻转
ABXYBA   ABYXBA

求出来的substring indices是 0:2 但是这个s1[0:2] 和 s2[0:2]一样,所以不行
同理common substring indices还是s[4:6] 和s2[4:6]一样,不行

而比如ABAD和 DABA

substring indice 一个是0:3, 一个是1:4,这样就没问题

思路2:

依次把每一个字符当做回文字符串的中间字符,找到以该字符为中间字符的回文串的最大长度。分别对奇偶的情况进行讨论,接下来的关键就是对边界的把握,确保下标不要越界。当子串已经包含首字符或最后一个字符且此时还是回文串的时候,下标分别会向两边多移一位,需要补回来。

参考https://shenjie1993.gitbooks.io/leetcode-python/content/005%20Longest%20Palindromic%20Substring.html

    class Solution(object):
        def longestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            """
            n = len(s)

            # empty or one char
            if n < 2:
                return s

            # left index of the target substring
            l = 0
            # right index of the target substring
            r = 0
            # length of the longest palindromic substring for now
            m = 0
            # length of the current substring
            c = 0

            # Whether the substring contains the first character or last character and is palindromic
            b = True
            for i in range(n):
                # Odd situation
                for j in range(min(n-i,i+1)):
                    if s[i-j] != s [i+j]:
                        b = False
                        break
                    else:
                        c = 2 * j + 1

                if c > m :
                    l = i - j + 1 - b
                    r = i + j + b
                    m = c 
                b = True

                # Even situation
                for j in range(min(n - i - 1, i + 1)):
                    if (s[i - j] != s[i + j + 1]):
                        b = False
                        break
                    else:
                        c = 2 * j + 2
                if (c > m):
                    l = i - j + 1 - b
                    r = i + j + 1 + b
                    m = c
                b = True
            return s[l:r]

以上是参考版本,自己写的版本:

    class Solution(object):
        def longestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            """
            n = len(s)

            m,l,r = 0,0,0

            for i in range(n):
                # odd case
                for j in range(min(i+1,n-i)):
                    if s[i-j] != s[i+j]:
                        break
                    if 2*j + 1 > m :
                        m = 2 * j + 1
                        l = i-j
                        r = i+j


                if i+1 < n and s[i] == s[i+1]:
                    for j in range(min(i+1,n-i-1)):
                        if s[i-j] != s[i+j+1]:
                            break
                        if 2 * j + 2 > m :
                            m = 2*j +2
                            l = i-j
                            r = i+j+1


            return s[l:r+1]

思路3:

Manacher算法

Manacher算法增加两个辅助变量id和mx,其中id表示最大回文子串中心的位置,mx则为id+P[id],也就是最大回文子串的边界。得到一个很重要的结论:

  • 如果mx > i,那么P[i] >= Min(P[2 * id - i], mx - i) . 为什么这样说呢,下面解释

下面,令j = 2*id - i,也就是说j是i关于id的对称点。

  • 当 mx - i > P[j] 的时候,以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中,由于i和j对称,以S[i]为中心的回文子串必然包含在以S[id]为中心的回文子串中,所以必有P[i] = P[j];

  • 当 P[j] >= mx - i 的时候,以S[j]为中心的回文子串不一定完全包含于以S[id]为中心的回文子串中,但是基于对称性可知,下图中两个绿框所包围的部分是相同的,也就是说以S[i]为中心的回文子串,其向右至少会扩张到mx的位置,也就是说 P[i] >= mx - i。至于mx之后的部分是否对称,再具体匹配。 所以P[i] >= Min(P[2 * id - i], mx - i),因为以j为中心的绘回文子串的左边界可能会比mx关于id的对称点要大,此时只能证明P[i]=P[2 * id - i]

  • 此外,对于 mx <= i 的情况,因为无法对 P[i]做更多的假设,只能让P[i] = 1,然后再去匹配。

在下面的程序中我的P数组保存的是,以当前字符为回文子串中心时,该回文子串的长度(不包含当前字符自身)

简单地用一个小例子来解释:原字符串为'qacbcaw',一眼就可以看出来最大回文子串是'acbca', 下面是我做的图,累shi了!

所以最终代码中的max_i就是字符'b'所对应的index8,start的值就是(max_i - P[max_i] - 1) / 2 = 1,最终输出结果为s[1:6],即‘acbca’

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        def preProcess(s):
            if not s:
                return ['^', '&']
            T = ['^']
            for i in s:
                T += ['#', i]
            T += ['#', '$']
            return T
        T = preProcess(s)
        P = [0] * len(T)
        id, mx = 0, 0
        for i in range(1, len(T)-1):
            j = 2 * id - i
            if mx > i:
                P[i] = min(P[j], mx-i)
            else:
                P[i]= 0
            while T[i+P[i]+1] == T[i-P[i]-1]:
                P[i] += 1
            if i + P[i] > mx:
                id, mx = i, i + P[i]
        max_i = P.index(max(P))    #保存的是当前最大回文子串中心位置的index
        start = (max_i - P[max_i] - 1) / 2
        res = s[start:start+P[max_i]]
        return res

run code的时候结果会跟expected不一样,但是该input确实2个结果都可以,所以放心地submit吧 还可以转到647题去看一看,也可以用这个算法解



回到顶部