問題描述
Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.
For example:
Given "aacecaaa", return "aaacecaaa".
Given "abcd", return "dcbabcd".
問題分析
一道hard題坛悉，還是不會，憂桑啊憂沙谐瘢……參考資料裸影。
首先對問題進行轉(zhuǎn)換。要通過在字符串s前面加字符使之成為一個回文串军熏，首先要找到s的最長回文前綴s1轩猩，設剩余部分為s2，那么將s2反轉(zhuǎn)和原s串拼接在一起荡澎，即可得到要求的回文串均践。
那么如何求這個最長回文前綴s1呢？這里用到KMP算法的next數(shù)組的求法摩幔。s = s1 + s2彤委，設置一個字符串tmp = s1 + s2 + ‘#’ + s2' + s1'，由于s1是最長回文前綴或衡，所以s1 = s1'焦影，連接時加一個‘#’是為了避免求得的s1超過s的長度，例如s = 'aaa'封断。
next數(shù)組的思想就是斯辰，在i位置處匹配成功了，但在i+1位置處匹配失敗了坡疼，如何移動子串進行下一步匹配彬呻，即如果在i+1處失敗了，那么下一位選取next[i]去匹配主串即可回梧。
因此我們對tmp字符串求next數(shù)組后废岂，next[-1]即為如果在最后一位成功匹配了，而下一位無法匹配時狱意，需要跳到tmp的什么位置，這個位置即為最長回味前綴的長度拯欧。
我的KMP算法代碼在這详囤。
AC代碼
class Solution(object):
def shortestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
n = len(s)
if n <= 1:
return s
tmp = s + '#' + s[::-1]
k = 0
next = [0 for i in range(len(tmp))]
for i in range(1, len(tmp)):
while k > 0 and tmp[i] != tmp[k]:
k = next[k-1]
if tmp[i] == tmp[k]:
k += 1
next[i] = k
return s[:next[-1]-1:-1] + s
Runtime: 82 ms, which beats 80.81% of Python submissions.
