其他
【打卡贴】（No.005）从零开始刷LeetCode
击上方“Ahab杂货铺”，选择“置顶公众号”
技术分享第一时间送达！
NO.5最长回文子串
原题：
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
示例 1：
输入: "babad"输出: "bab"注意: "aba"也是一个有效答案。示例 2：
输入: "cbbd"输出: "bb"简单粗暴来求一个字符串的最长回文子串，我们可以将以每个字符为首的子串都遍历一遍，判断是否为回文，如果是回文，再判断最大长度的回文子串。算法简单，但是算法复杂度太高。
l = len(s)
max_length = 0
p = ''
if len(s) == 1:
return s
for i in range(l):
for j in range(i + 1, l):
is_p = True
for k in range(i, int((i + j) / 2) + 1):
if s[k] != s[j - k + i]:
is_p = False
break
if is_p and (j - i + 1) > max_length:
max_length = j - i + 1
p = s[i:j + 1]
if p == '':
p = s[0]
return p
第二种方法来源网络
有两个主要的步骤:
将所有可能的奇数/偶数长度的回文子串都转换成了奇数长度：在每个字符的两边都插入一个特殊的符号。abba => #a#b#b#a#， aba => #a#b#a#
用数组 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
def manacher(self):
# 字符串处理，
# 用特殊字符隔离字符串方便处理偶数子串
s = '#' + '#'.join(self.string) + '#'
lens = len(s)
# 辅助列表：
# f[i]表示i作中心的最长回文子串的长度
f = []
# 记录对i右边影响最大的字符位置j
maxj = 0
# 记录j影响范围的右边界
maxl = 0
# 记录最长的回文子串长度
maxd = 0
# 遍历字符串
for i in range(lens):
if maxl > i:
# 这里为了方便后续计算使用count，
# 其表示当前字符到
#其影响范围的右边界的距离
count = min(maxl-i, int(f[2*maxj-i]/2)+1)
else :
count = 1
# 两边扩展
while i-count >= 0 and i+count \
< lens and s[i-count] == s[i+count]:
count += 1
# 更新影响范围最大的字符j及其右边界
if(i-1+count) > maxl:
maxl, maxj = i-1+count, i
f.append(count*2-1)
# 更新回文子串最长长度
maxd = max(maxd, f[i])
# 去除特殊字符
return int((maxd+1)/2)-1
公众号做了已经一周，关注每天都会增长，在巩固自己知识的同时还能认识这么多热爱编程的小伙伴，是一件挺开心的事情，会继续坚持下去。