Python 版 LeetCode 刷题笔记 #5 无重复字符的最长子串（下）
Python 版 LeetCode 刷题笔记 #5 无重复字符的最长子串（下）
今天接着研究这个第五题，先回顾下题目：
题目
第 5 题 无重复字符的最长子串：
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例:
输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。
输入: "cbbd" 输出: "bb"思路
昨天我以为自己尝试的方法属于暴力穷举，现在想来算不上。真正的暴力穷举应该是将该字符串所有的子串找出来，检测是否是回文，并将最长的回文子串返回。
我昨天的思路呢，是以该字符串的每个字符为子串中心，向左向右两侧检测直到不匹配，这应该算“中心扩散法”。因为我对其中重复出现的字符做了一番处理（比如专门建了字典来储存每个字符出现的位置，用于检测重复字符的出现），可能有些画蛇添足，导致表现不如其它“中心扩散法”的代码表现好。
但这个思路仍然需要对每个字符来进行检测，每对新的字符来进行检测，都是全新、独立的一个检测流程，并不能利用到之前做过的检测工作。既然是要找回文子串，回文的特点是关于中心对称，那么利用这个特点来利用起之前做的匹配检测无疑将会大大压缩工作量，这也是 Manacher算法（俗称“马拉车”，音译吧）能大大降低时间复杂度的原因。
翻阅了诸多关于该算法的介绍文章后，我觉得如果之前对此没概念、可以先看下面两篇相关算法的文章：
- 字符串匹配的KMP算法http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
- [译+改]最长回文子串(Longest Palindromic Substring) Part II https://www.cnblogs.com/bitzhuwei/p/Longest-Palindromic-Substring-Part-II.html
这是我翻看的里面算是新手友好的解读，看完之后才逐渐对这算法有了些清晰的概念。
代码
class Solution:
def longestPalindrome(self, s: str) -> str:
# 空白字符串单独处理
if len(s)== 0:
return ""
# 全部是单一重复字符单独处理，例如“aaaaaa”
c_set = set(s)
if len(c_set)==1:
return s
# Manacher 算法/马拉车算法
# 现在字符串中间加额外符号，无论长度奇偶都会统一成奇数位的字符串方便回文检测
t = '#' + '#'.join(s) + '#'
#print(t) #此时 t 变成了 "#a#b#b#c#c#c#b#b#a#"
l = len(t)
# 数组 p 记录检测过的回文子串的信息,初始化等长的 0 列表
p = [0 for i in range(l)]
print(p)
# 根据算法，确立 max_right:向右扩展的最远边界
max_right = 0
# center:max_right 的回文中心的索引值
center = 0
# 当前遍历的中心最大扩散步数，其值等于原始字符串的最长回文子串的长度
max_len = 1
# 原始字符串的最长回文子串的起始位置，与 max_len 必须同时更新
start = 1
for i in range(l):
if i < max_right:
mirror = 2 * center - i
# 这一行代码是 Manacher 算法的关键所在，要结合图形来理解
p[i] = min(max_right - i, p[mirror])
# 下一次尝试扩散的左右起点，能扩散的步数直接加到 p[i] 中
left = i - (1 + p[i])
right = i + (1 + p[i])
# left >= 0 and right < l 保证不越界
# t[left] == t[right] 表示可以扩散 1 次
while left >= 0 and right < l and t[left] == t[right]:
p[i] += 1
left -= 1
right += 1
# 根据 max_right 的定义，它是遍历过的 i 的 i + p[i] 的最大者
# 如果 max_right 的值越大，进入上面 i < max_right 的判断的可能性就越大，这样就可以重复利用之前判断过的回文信息了
if i + p[i] > max_right:
# max_right 和 center 需要同时更新
max_right = i + p[i]
center = i
if p[i] > max_len:
# 记录最长回文子串的长度和相应它在原始字符串中的起点
max_len = p[i]
start = (i - max_len) // 2
return s[start: start + max_len] 提交答案
基于数学家的算法性能自然有了质的提升：
中文区结果：
执行用时 :88 ms, 在所有 Python3 提交中击败了97.01%的用户 内存消耗 :13.7 MB, 在所有 Python3 提交中击败了9.26%的用户
英文版结果：
Runtime: 76 ms, faster than 96.26% of Python3 online submissions for Longest Palindromic Substring. Memory Usage: 14.1 MB, less than 20.17% of Python3 online submissions for Longest Palindromic Substring.
当然，这代码并不是我独立完成的，照着算法的葫芦和其它推荐答案中的代码来仿写的，开头单独加了个重复字符的特殊处理。
结论
这个算法好用是好用，但基于数学家算法的基础上来做的，感觉也只能熟记多练几遍之后来应用了。在翻阅其它文章时看到这么句话：“这个算法是 non-trivial 的，没人会在面试时要求你给出这么霸气的东西。不过，如果你能读到这里并理解到这里，值得给自己一个大大的奖励了！”还挺暖心的。
这次算是有个印象，之后有机会再多练练吧。