[TOC]
并查集
128. 最长连续序列
130. 被围绕的区域
200. 岛屿数量
Manacher’s Algorithm(马拉车算法)
647. 回文子串
214. 最短回文串
Hierholzer算法
332. 重新安排行程
753. 破解保险箱
KMP算法
算法讲解: https://zhuanlan.zhihu.com/p/83334559
算法视频讲解: https://www.bilibili.com/video/BV1PA411h7VY?from=search&seid=6756106598847924706
# 构建nxt数组,表示模式串的的最长公共前后缀的长度
def build (p):
m = len(p)
nxt = [0,0]
j = 0
for i in range(1, m):
while j > 0 and p[i] != p[j]:
j = nxt[j]
if p[i] == p[j]:
j += 1
nxt.append(j)
return nxt
# s与p(模式串)的匹配
def match(s, p):
m, n = len(p), len(s)
nxt = build(p)
ans = []
j = 0
for i in range(n):
while j > 0 and s[i] != p[j]:
j = nxt[j]
if s[i] == p[j]:
j += 1
if j == m:
ans.append(i - m + 1)
j = nxt[j]
return ans
214. 最短回文串
# 找寻最长前缀回文串
# KMP 算法
# 反序的s作为待匹配的字符串s
# 正序的s作为模式串p
# 当匹配到s(待匹配的字符串)的最后一个时,p的坐标i说明前i个字符就是最长的前缀回文串
class Solution:
def shortestPalindrome(self, s: str) -> str:
if not s: return ''
def build(p):
m = len(p)
nxt = [0,0]
j = 0
for i in range(1, m):
while j >0 and p[i] != p[j]:
j = nxt[j]
if p[i] == p[j]:
j += 1
nxt.append(j)
return nxt
def match(s, p):
m, n = len(p), len(s)
nxt = build(p)
# print(nxt)
j = 0
for i in range(n):
while j > 0 and s[i] != p[j]:
j = nxt[j]
if s[i] == p[j]:
j += 1
return j
p = s
s = s[::-1]
index = match(s, p)
# print(index)
return p[index:][::-1] + p