LeetCode刷题实战5:判断回文子串
共 4505字,需浏览 10分钟
·
2020-08-11 20:45
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
https://leetcode.com/problems/longest-palindromic-substring/
翻译
给定一个字符串s,要求它当中的最长回文子串。可以假设s串的长度最大是1000。
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"
这道题中利用回文串的性质还有一个trick,对于一个字符串S,如果我们对它进行翻转,得到S_,显然它当中的回文子串并不会发生变化。所以如果我们对翻转前后的两个字符串求最长公共子序列的话,得到的结果就是回文子串。
算法导论当中对这个问题的讲解是使用动态规划算法,即是对于字符串S中所有的位置i和S_中所有的位置j,我们用一个dp数组记录下以i和j结尾的S和S_的子串能够组成的公共子序列的最大的结果。
显然,对于i=0,j=0,dp[i][j] = 0(假设字符串下标从1开始)
我们写出DP的代码:
for i in range(1, n):
for j in range(1, m):
if S[i] == S_[j]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
我们不难观察出来,这种解法的复杂度同样是。并且空间复杂度也是O(n),也就是说我们费了这么大劲,并没有起到任何优化。所以从这个角度来看,暴力搜索并不是这题当中很糟糕的解法。
分析到了这里,也差不多了,下面我们直接进入正题,这题的最佳解法,O(n)时间内获取最大回文子串的曼彻斯特算法。
预处理的代码:
def preprocess(text):
new_str = '#'
for c in text:
new_str += c + '#'
return new_str
曼切斯特算法用到三个变量,分别是数组p,idx和mr。我们接下来一个一个介绍。
首先是数组radis,它当中存在的是每个位置能构成的最长回文串的半径。注意,这里不是长度,是半径。
我们举个例子:
字符串S # a # b # b # a #
radis 1 2 1 2 5 2 1 2 1
此时i小于mr,mr对应的回文中心是id。那么i在id的回文范围当中,对于i而言,我们可以获取到它关于id的对称位置:id * 2 - i,我们令它等于i_。知道这个对称的位置有什么用呢?很简单,我们可以快速的确定radis[i]的下界。在遍历到i的时候,我们已经有了i_位置的结果。通过i_位置的结果,我们可以推算i位置的范围。
radis[i] >= min(radis[i_], mr-i)
为什么是这个结果呢?
我们把情况写全,假设mr-i > radis[i_]。那么i_位置的回文串全部都落在id位置的回文串里。这个时候,我们可以确定radis[i]=radis[i_]。为什么呢?
因为根据对称原理,如果以i为中心的回文串更长的话,我们假设它的长度是radis[i_]+1。会导致什么后果呢?如果这个发生,那么根据关于id的对称性,这个字符串关于id的对称位置也是回文的。那么radis[i_1]也应该是这么多才对,这就构成了矛盾。如果你从文字描述看不明白的话,我们来看下面这个例子:
S: c a b c b d b c b a c
radis: x_ i_ 5 i x
字符串S XXXXXXXXSXXXXXXXXXXXXXXX
radis i_ id i mr
在上图这个例子当中,i_的位置的回文串向左只能延伸到ml,因为ml-1的位置和关于i_对称的位置不相等。对于mr的右侧,它完全可以既和i点对称,又不会影响raids[id]的正确性。这个时候,我们就可以通过循环继续遍历,拓展i位置的回文串。
整个过程的分析虽然很多,也很复杂,但是写成代码却并不多。
# 初始化
idx, mr = 0, 0
# 为了防止超界,设置字符串从1开始
for i in range(1, n):
# 通过对称性直接计算radis[i]
radis[i] = 1 if mr < i else min(radis[2 * idx - i], mr - i)
# 只有radis[i_] = mr - i的时候才继续往下判断
if radis[2 * idx - i] != mr - i and mr > i:
continue
# 继续往下判断后面的位置
while s[radis[i] + i] == s[i - radis[i]]:
radis[i] += 1
# 更新idx和mr的位置
if radis[i] + i > mr:
mr = radis[i] + i
idx = i
到这里,曼切斯特算法就算是实现完了。虽然我们用了这么多篇幅去介绍它,可是真正写出来,它只有几行代码而已。不得不说,实在是非常巧妙,第一次学习可能需要反复思考,才能真正理解。
不过我们还有一个问题没有解决,为什么这样一个两重循环的算法会是 O(n)的复杂度呢?
想要理解这一点,需要我们抛开所有的虚幻来直视本质。虽然我们并不知道循环进行了多少次,但是有两点可以肯定。通过这两点,我们就可以抓到复杂度的本质。
第一点,mr是递增的,只会变大,不会减小。
第二点,mr的范围是0到n,每次mr增加的数量就是循环的次数。
所以即使我们不知道mr变化了多少次,每次变化了多少,我们依然可以确定,这是一个O(n)的算法。
如果喜欢本文,请顺手点个赞或者转发吧。
上期推文: