LeetCode攀登之旅(5)
LeetCode攀登之旅(5)
LeetCode攀登之旅(5)
0.说在前面
1.暴力解法
2.中心枚举法
3.动态规划法
4.马拉车法
5.参考文章
6.作者的话
0.说在前面
本节从求长回文子串问题，给出四种解题方法，并深入分析马拉车与动态规划算法。
【Question】
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"1.暴力解法
【思想】
定义一个字典，并赋给初值为空，表示如果原先所给字符为空字符，直接返回，防止出现indexerror。
算法中有三层循环，对没错，三层，所以你去跑leetcode，通不过，直接超出时间限制！
但是这是一种思想，得掌握，接下来说说三层循环干了什么事情。
外一层循环，for循环直接遍历目标字符的长度！
中二层循环，for循环从上层的index访问到结尾！
内三层循环，while循环，这里是算法核心，分别用两个变量存储前后的变量，然后向内靠拢，判断是否相同，若相同，则继续比对，不相等，则直接退出本次while循环。
每次在中二层循环吗，添加了个count,当前面定义的收尾元素分别颠倒大小时候，即为一个回文子串，然后重新计算count，并将其与maxcount比对。然后讲初始与末尾的数进行切片即为真实的回文子串。
【code】
class Solution:
def longestPalindrome(self, s):
s_len = len(s)
maxcount=0
s_new = {'0': ''}
for j in range(s_len):
for k in range(j,s_len):
count = 0
l, m=j, k
while m >= l:
if s[l] == s[m]:
l, m = l+1, m-1
else:
break
if m < l:
count = k - j + 1
if maxcount < count:
maxcount = count
s_new['0']=s[j:k+1]
return s_new['0']
s = Solution()
a = s.longestPalindrome('babd')
print(a)2.中心枚举法
【思想】
这个方法是基于上述方法的改进，每次从中心向两边进行扩展比对。这个算法的注意点为，奇数与偶数问题，也就是说需要考虑目标字符串为奇数，还是偶数的问题。
【code】
class Solution:
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
l = len(s)
if l<=1:
return s
# 定义最长回文串
long_palindrome = ''
for i in range(l-1):
# 奇偶问题合并处理:p1与p2
p1 = self.center_expand(s,i,i)
if len(p1)>len(long_palindrome):
long_palindrome=p1、
p2 = self.center_expand(s,i,i+1)
if len(p2)>len(long_palindrome):
long_palindrome=p2
return long_palindrome
def center_expand(self,s,left,right):
s_len = len(s)
while left>=0 and right<s_len and s[left]==s[right]:
left-=1
right+=1
# 上述循环后,left与right是不相等的字符，所以截取字符串,是letf+1,right
return s[left+1:right]
s = Solution()
a = s.longestPalindrome('abab')
print(a)3.动态规划法
【思想】
上一节的0-1背包问题实现就是动态规划法的典型例子。这个算法的核心这里用之前看到的一句英文解释:
Those who cannot remember the past are condemned to repeat it.
这句话的意思是，动态规划的思想是记住已经求过的解。对于动态规划的具体解释，会在今后仔细研究的算法导论中给大家解释。
这里再以当前求最大回文子串来了解一下动态规划法的思想。
'''
分为三种情况：
第一种:检测目标子串长度为1;
第三种:检测目标子串长度为2;
第四种:检测目标子串长度大于等于3;
'''首先生成一个二维数组，然后根据遍历的情况是否为回文子串，标记True or False。
根据上述三种情况，下面仔细说明，并以一个实际例子进行手写推导。
第一种：当所检测的子串长度为1时，毋庸置疑，必然是回文串，直接标记为True；
第二种：当所检测的子串长度为2时，只需要判断当前与下一个元素是否想的女即可确定该子串是否是回文串；
第三种：当所检测的子串长度超过2时，直接从子串长度为3进行，因为前面两种情况已经把子串长度为1或2运算过了，那么这个就是dp算法的核心，对于之前已经运算过的不需要重新去运算，进而减少了时间复杂度的运算。
在第三种情况中，直接以3为跨步，便可以访问到每个子串的末尾的字符，那么当当前位置的字符与末尾字符相等，并且通过访问之前已经存储过的True or Fals进行比对，也就是s[i] == s[j] and dp[i + 1][j - 1]这行，这行请仔细琢磨，为dp算法的核心之处！非常重要！
【code】
class Solution:
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
# 获取字符串的长度
s_len = len(s)
# 生成dp算法的二维数组
dp = [[0] * s_len for i in range(s_len)]
if s_len == 0:
return s
# 最大长度
maxLen = 1
# 第一种：检查目标子串长度为1
i = 0
while i < s_len:
dp[i][i] = True
i += 1
# 第二种：检查目标子串长度为2
start = 0
i = 0
while i < s_len - 1:
if s[i] == s[i + 1]:
dp[i][i + 1] = True
start = i
maxLen = 2
i += 1
# 第三种：检查目标子串长度为大于等于3
# 遍历长度
pal_num = 3
while pal_num <= s_len:
i = 0
# 表示循环子串长度为pal_num时,有n-pal_num+1种组合
while i < (s_len - pal_num + 1):
# 定义子串末尾
j = i + pal_num - 1
# 只有再中间的数为True且两边一样的情况下，才可以将其作为回文子串
if s[i] == s[j] and dp[i + 1][j - 1]:
dp[i][j] = True
if pal_num > maxLen:
start = i
maxLen = pal_num
i += 1
pal_num += 1
return s[start:start + maxLen]【手推】
子串长度为1图
子串长度为2图
子串长度总图
4.马拉车法
【思想】
对于第二种中心枚举法我们知道，必须对奇数或偶数进行讨论，那么这就造成了不同的回文串中心位置。
而且对于第二种方法，存在子串被重复多次访问，造成时间的浪费，那么我们想一下，能不能采用一种算法直接达到线性算法的时间，并且可以解决上述两个问题呢。
这里就引出了Manacher简称马拉车算法，这个算法非常晦涩难懂，仔细阅读后，而且在ACM大赛上不怎么常用，一般想到上述的dp算法，就可以了，但是我们现在是精益求精，多学几个思想，没什么坏出。而且这个马拉车算法确实能学到很多不同的思想，如下面思想介绍。
首先解决第一个问题：原字符串奇数与偶数问题。
这个问题在马拉车中，是通过添加特殊字符解决的，比如给定字符串abba，这个字符串为偶数，那么插入特殊字符后，就会变为#a#b#b#a#,长度变为9，变为奇数，这个思想将所有的偶数与奇数字符串统一处理为奇数字符串！
另一个问题也就是通俗的效率问题，解决重复多次访问的问题。这个直接从马拉车算法思想中去体会。
假设原字符串为S=dabbac，那么经过插入特殊字符变为#d#a#b#b#a#c#,并即为S1[i]。
在马拉车算法中，通常使用一个新数组P[i]用于记录以字符S1[i]为中心的最长回文子串向左或向右扩张的长度，也就是回文串长度的一半，例如：
S1 # d # a # b # b # a # c #
P 1 2 1 2 1 2 5 2 1 2 1 2 1
i 0 1 2 3 4 5 6 7 8 9 10 11 12
P[i]-1 0 1 0 1 0 1 4 1 0 1 0 1 0可以看出上述P[i]-1正好是原字符串中回文串的总长度
【证明过程】
首先在转换得到的字符串S1中，所有的回文字串的长度都为奇数，那么对于以S1[i]为中心的最长回文字串，其长度就为2*P[i]-1,经过观察可知，S1中所有的回文子串，其中分隔符的数量一定比其他字符的数量多1，也就是有S1[i]个分隔符，剩下S1[i]-1个字符来自原字符串，所以该回文串在原字符串中的长度就为P[i]-1
这里解释一下上述P[i]怎么算出来的以及上面那句话的解释！
P[0]=1 因为#号左右两边不相等，直接为1，P[1]=2 因为#d#，d的前后各有一个#刚好构成一个回文子串，然后取子串的中心位置向左或向右扩张的长度，扩张各位1，再加上本身，即为2。后面的按照此方法推导即可！
以上述的字符d为例，p[1]-1=2-1=1，原字符串dabbac，可以看到d为第一个字符，以d为中心的回文子串长度为1。
【P数组计算】
该算法增加两个辅助变量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 的对称点(j = id - (i - id))
if (mx - i > P[j])
P[i] = P[j];
else /* P[j] >= mx - i */
P[i] = mx - i; // P[i] >= mx - i，取最小值，之后再匹配更新。第一种情况：mx>i
当 mx - i > P[j] 的时候，以S1[j]为中心的回文子串包含在以S[id]为中心的回文子串中，由于 i 和 j 对称，以S1[i]为中心的回文子串必然包含在以S1[id]为中心的回文子串中，所以必有 P[i] = P[j]
mx - i > P[j] 图
当 mx - i <=P[j] 的时候以j为对称轴的回文串很长,只有下图中绿色标注的地方一致
mx>mx - i <=P[j] 图
不论上述哪种情况，之后都要更新mx与id,因为有可能得到更大的mx!
第二种情况：mx<=i
说明以i为对称轴的回文串还没有任何一个部分被访问过，于是只能从i的左右两边开始尝试扩展了，当左右两边字符不同，或者到达字符串边界时停止，只能P[i] = 1，然后再去匹配了。
【code】
class Solution:
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
#预处理
t='#'+'#'.join(s)+'#'
RL=[0]*len(t)
MaxRight=0
pos=0
# MaxLen=0
for i in range(len(t)):
if i<MaxRight:
# 或者RL[i]=min(RL[2*pos-i], MaxRight-i)
# 上述注释掉的这行代码直接等价于下面5行代码
j=2*pos-i
if MaxRight-i>RL[j]:
RL[i]=RL[j]
else:
RL[i]=MaxRight-i
else:
RL[i]=1
#尝试扩展，注意处理边界
while i-RL[i]>=0 and i+RL[i]<len(t) and t[i-RL[i]]==t[i+RL[i]]:
RL[i]+=1
#更新MaxRight,pos
if RL[i] >= RL[pos]:
MaxRight = RL[i] + i - 1
pos = i
'''
if RL[i]+i-1>MaxRight:
MaxRight=RL[i]+i-1
pos=i
#更新最长回文串的长度
MaxLen=max(MaxLen, RL[i])
return MaxLen-1
'''
a=int((2*pos-MaxRight)/2)
b=int(MaxRight/2)
return s[a:b]
s = Solution()
a = s.longestPalindrome('abab')
print(a)5.参考文章
- Manacher's ALGORITHM: O(n)时间求字符串的最长回文子串
- 马拉车（Manacher）算法最通俗教学
- 最长回文子串-Manacher算法
6.作者的话
最后，您如果觉得本公众号对您有帮助，欢迎您多多支持，转发，谢谢！ 更多刷题，请关注本公众号算法系列！