4ec9d5f608044796019b289873ffeb53
Problem 5: Longest Palindromic Substring

Problem 5: Longest Palindromic Substring

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

难度等级:Medium(中等)

题干

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

题意

给定一个字符串,找出字符串当中最长的回文子串。

样例

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: "cbbd"
Output: "bb"

分析

这题虽然给的难度是中等,但其实并不简单,对于没接触过的同学来说是有点难度的。

最简单的当然是暴力,我们枚举字符串当中的所有位置作为回文串的中间对称位置,然后遍历能够往左右两边延伸达到的最长的长度。记录下那个最长的值,就是答案了。

先别嫌弃暴力low,在这道题当中,暴力已经算得上是一个比较不错的算法了。不相信,我们再说另一个方法,做一下对比大家就能发现了。

如果大家对于回文这个概念足够敏感的话,很容易想到一个trick。假设当下我们有一个字符串S,还有一个字符串S‘,其中S’是S字符串的翻转得到的对称字符串。那么S当中的最长回文串就等于S和S‘的最长公共子串。

如果学过算法导论的同学想必对于最长公共子序列非常熟悉,最长公共子串和最长公共子序列非常近似,唯一不同的就是子串要求字符串必须是连续的,而子序列则可以不连续,但除此之外解法都很类似,当然还是万能的dp大法。

写成伪代码:

for i in range(n):
    for j in range(m):
        if s[i] == s'[j]:
            dp[i][j] = dp[i-1][j-1]+1

虽然针对这个问题还有很多的优化,但是不论怎么优化,空间复杂度可以到O(n),但是时间复杂度还是O(n^2)。

而我们使用暴力求解呢?也不过是这个复杂度,而且最关键的是,暴力的编码复杂度和空间复杂度都要更低。所以,在这道问题当中,暴力其实算得上是个不错的算法了。

当然,这不是最优的算法。

有一个专门用来解决回文串问题的算法,叫做曼切斯特算法。英文是manchester algorithm。

曼彻斯特算法非常巧妙,可以在O(n)的时间内计算出最长的回文子串。

回文串有一个天生的难点在于长度为奇数的回文串和长度为偶数的回文串是不同的,长度为奇数的回文串对称中心在中间一个字符上,例如aba,对称点就是b。而偶数的回文串对称点则在中间,比如abba,的对称点就在两个字母b当中。

为了解决这个问题,曼彻斯特算法先对字符串做一个预处理,在每两个字符中间全部填入一个特殊字符,比如’#’,如此一来所有的回文串都变成了奇数长度的情况。

比如:abba -> #a#b#b#a#。

回文中心就在’#‘上了,而aba -> #a#b#a#回文中心还是在b上,长度依然为奇数。

我们用一个数组p,来存储每个回文串对称点的长度半径。

比如:

# a # b # b # a #
1 2 1 2 5 2 1 2 1

对于i位置来说,半径长度是p[i],那么以i为中心的回文串的长度是多少呢?我们不妨计算一下,由于加入了#之后,所有的回文串都是奇数长度的。所以完整的长度是多少呢?

很简单p[i]* 2 - 1对吧,这个长度是个奇数,找下规律很容易发现在这个字符串当中#的数量要比字符多一个。所以字符串原文的长度就是(p[i] * 2 - 1 - 1) / 2。

p[i]-1就是我们要求的答案,也就是说我们把最终的答案和我们要求的p[i]关联上了。

有了这个p数组之后,我们就可以利用i位置前面的p数组当中的信息来优化p[i]的求解过程,从而最终在一个很高效的时间内找出最优解。

为了达成这个目的,我们还需要引入两个变量。其中一个叫做mr,一个叫做id。mr是most right的缩写,意思是最右边的位置。id顾名思义,就是某一个id。这两个变量用来干嘛的呢?

很简单,用来记录在当前位置之前,向右延伸到最远的位置和最远位置对应的id,下面举个例子:

... # c # [ # a # a # b # b # a # a # b # b # a # a # ] d # …
… 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

在上面这个字符串当中,当当下的i指向13之后的位置时,用[]扩起来的地方是当下所能找到的最长的回文子串,这个回文串中间点的位置在13,而所能延伸到的最右侧位置是23。很显然,id=13,mr=23。

那么,这两个变量有什么作用呢?

假设,当前i的位置在14,由于14 < 23,那么说明14被包括在了之前id位置的回文子串当中。因为这一点,所以我们就可以利用上回文串的特性。很方便地计算出i位置下的回文串的长度。

当然,利用这些信息,还是不足以直接计算出P[i]的值的。但是我们可以确定它的下届。用公式表达出来是这样的: min(mr - i, p[id * 2 - i])

也就是i位置距离mr位置的距离,和i关于id位置对称点的p值。

假设mr - i > p[id * 2 - i],说明I距离mr的距离大于它对称点的对称半径。为什么用对称点的对称半径作为下届呢?因为根据对称性,如果p[i] > p[id * 2 - i],说明至少在i + p[id * 2 -1] + 1的位置还能构成一个对称。因为mr - i > p[id * 2- i],所以可以肯定,i + p[id * 2 -1] + 1关于id 的对称点也在[]标记的范围之内。既然在这个范围内,根据回文串的对称性,那么p[id * 2 - i]位置的回文串也应该把它包含在内才对。

假设p[id * 2 - i] > mr - i,说明i对称的位置的回文串的最左侧已经抵达了整个回文串的最左侧。这种情况下,根据上文当中相同的原理,我们也可以确定p[i] = p[id * 2 - i]。为什么不可能更大呢?因为如果p[i]大于这个值,那么说明在mr的右侧,依然能够构成回文。由于p[id * 2- i]是大于 mr - i的,如果说mr右侧的元素也能构成回文,那么就说明之前以id为中心点的回文串长度计算错误,至少还能向右延伸。

举个极端的例子:

a[xxxx … 2*id-i, xxxx… id xxxx … i xxx mr]a

如果mr右侧的a能够构成回文,因为2*id-i位置的回文串长度是大于mr-i的,说明至少区间最左侧的a也是回文串的一部分。根据对称性,那么mr右侧的a必然和左侧的a对称,那么说明之前id的区间计算有误。这会导致矛盾,所以一定不会发生。也就是说p[id * 2 - i] > mr - i时,我们也可以确定p[i] = mr - i

最后一种情况,就是当两者相等的时候。这种情况需要进一步探讨i位置的对称向右延伸的可能。当p[id * 2 - i] = mr - i时,说明以i为中心的回文串,向右至少能够延伸到mr,那么mr右侧的位置有没有可能可以增加回文串的长度呢?其实是有可能的。

还用刚刚的例子:

a[xxxx … 2*id-i, xxxx… id xxxx … i xxx mr]X

因为p[id * 2 -I]是等于mr- i的,可以证明mr右侧的元素一定不是a。既然不是a,那么就有可能构成新的回文,所以我们需要加以判断,并一直向右延伸。

至此,我们就利用i位置之前的信息,推出了i位置的所有可能性。

把整个递推公式写成伪代码如下:

for i in range(n):
    p[i] = min(p[id * 2 - i], mr - i)
    if p[id * 2 - i] != mr - i:
        continue
    while s[i - p[i]] == s[i + p[i]]:
        p[i] ++
    if p[i] + i > mr:
        mr = p[i] + i
        id = i
top Created with Sketch.