前幾天的
學了一下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