前几天的
学了一下KMP
可以利用KMP算最长 prefix=suffix的这一步 来求这题
这题简而言之就是在求最长回文prefix
所以可以直接看new_s = s + s[::-1]
算最长prefix=suffix on new_s时 就可以顺便求出答案
不过要注意的是
有一种特殊case
ex: aabba
这时new_s 会是 aabbaabbaa
然后你求出的最长prefix = suffix会是 aabbaa 长度是6
但很明显这超出了原本s的长度 它重复算到了
所以有个很tricky的方式是把new_s定义成 s+'#'+s[::-1]
中间用一个#隔开
就不会越界了
def shortestPalindrome(self, s: str) -> str:
if s == "":
return ""
#KMP
s_new = s + "#" + s[::-1]
kmp_arr = [0 for _ in range(len(s_new))]
kmp_arr[0] = 0
for i in range(1, len(kmp_arr)):
j = kmp_arr[i-1]
while j>0 and s_new[i] != s_new[j]:
j = kmp_arr[j-1]
kmp_arr[i] = j+(s_new[i]==s_new[j])
# print(kmp_arr[-1])
return "".join(reversed(s[kmp_arr[-1]:]))+s