问题描述
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题，还是不会，忧桑啊忧桑……参考资料。
首先对问题进行转换。要通过在字符串s前面加字符使之成为一个回文串，首先要找到s的最长回文前缀s1，设剩余部分为s2，那么将s2反转和原s串拼接在一起，即可得到要求的回文串。
那么如何求这个最长回文前缀s1呢？这里用到KMP算法的next数组的求法。s = s1 + s2，设置一个字符串tmp = s1 + s2 + ‘#’ + s2' + s1'，由于s1是最长回文前缀，所以s1 = s1'，连接时加一个‘#’是为了避免求得的s1超过s的长度，例如s = 'aaa'。
next数组的思想就是，在i位置处匹配成功了，但在i+1位置处匹配失败了，如何移动子串进行下一步匹配，即如果在i+1处失败了，那么下一位选取next[i]去匹配主串即可。
因此我们对tmp字符串求next数组后，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.
