难度: Hard
原题连接
内容描述
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.
Example 1:
Input: "aacecaaa"
Output: "aaacecaaa"
Example 2:
Input: "abcd"
Output: "dcbabcd"
思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(N)******
直接暴力，看看最长回文前缀字符串是谁然后在它前面加上其后缀的逆序即可，即suff[::-1] + pref + suff
太慢了，beats 8.34%
class Solution(object):
def shortestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
for i in range(len(s), -1, -1):
pref, suff = s[:i], s[i:]
if pref == pref[::-1]:
return suff[::-1] + s思路 2 - 时间复杂度: O(N^2)- 空间复杂度: O(N)******
优化一些，我们将这个字符串的逆序与这个字符串本身做对比
例如
abcd， 其逆序为dcba
我们先看abcd是否以 dcba开头
abcd
dcba
发现并不是，将dcba左移一位
我们再看abcd是否以 cba开头
abcd
dcba
发现并不是，将cba左移一位
我们再看abcd是否以ba开头
abcd
dcba
发现并不是，将ba左移一位
我们再看abcd是否以a开头
abcd
dcba
发现abcd以a为开头，则知道了可以将dcb + abcd作为结果
beats 55.25%
class Solution(object):
def shortestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
reversed_s = s[::-1]
for i in range(len(s)):
if s.startswith(reversed_s[i:]): # 说明s[:n-i]是回文
return reversed_s[:i] + s
return s思路 3 - 时间复杂度: O(N^2)- 空间复杂度: O(N)******
递归求s的最长回文前缀字符串，然后与思路1一样返回suff[::-1] + pref + suff即可
beats 99.69%
class Solution(object):
def shortestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
i = 0
for j in range(len(s)-1, -1, -1):
if s[i] == s[j]:
i += 1
if i == len(s):
return s
tmp = s[i:][::-1]
return tmp + self.shortestPalindrome(s[:i]) + s[i:]思路 4 - 时间复杂度: O(N)- 空间复杂度: O(N)******
用manacher算法来算出s的最长回文前缀字符串
因为满足P[i] == i，则说明从i往前往后可以构造出一个回文字符串，且这个回文字符串是s的前缀字符串
假设P数组中最后一个满足P[i] == i的坐标为idx，idx记录s的最长回文前缀字符串的中心坐标，则其在s中对应的坐标为P[idx]
最长回文前缀字符串就是s[:idx]，因为P数组中还有'#'的额外字符
可能是因为这道题的测试用例的问题，才beats 60.19%
class Solution(object):
def shortestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if not s or len(s) == 0:
return ''
def preProcess(s):
if not s:
return ['^', '&']
T = ['^']
for i in s:
T += ['#', i]
T += ['#', '$']
return T
T = preProcess(s)
P = [0] * len(T)
id, mx = 0, 0
for i in range(1, len(T)-1):
j = 2 * id - i
if mx > i:
P[i] = min(P[j], mx-i)
else:
P[i]= 0
while T[i+P[i]+1] == T[i-P[i]-1]:
P[i] += 1
if i + P[i] > mx:
id, mx = i, i + P[i]
P = P[1:-1]
idx = -1 # idx记录s的最长回文前缀字符串的中心坐标
for i in range(len(P)-1, -1, -1):
if P[i] == i:
idx = i
break
return s[P[idx]:][::-1] + s思路 5 - 时间复杂度: O(N)- 空间复杂度: O(N)******
求s的最长回文前缀字符串，然后与思路1一样返回suff[::-1] + pref + suff即可
把题目转换求这个之后，我们看到了最长回文前缀字符串，这不是可以转化成求最长的前缀后缀相等的长度吗？
我们可以自己构造一个回文字符串，例如对于"aacecaaa"，我们构造 pattern = "aacecaaa" + ‘#’ + ‘aaacecaa’，那么pattern现在是个回文字符串，我们再对其进行findLPS操作（KMP），发现其最长前缀和后缀相等的长度就是7，即 'aacecaa' == 'aacecaa'，因为本身我们满足了pattern是个回文字符串，它的某个前缀'aacecaa'等于它的某个后缀'aacecaa'，那么同时它的后缀的逆序又是等于它的这个前缀的(回文性质)，即 suff == suff[::-1] == pref
所以我们就求出来了最长回文前缀字符串，在这里它就是 pref == suff == suff[::-1] == 'aacecaa'
求出了s的最长回文前缀字符串的长度lps[-1]之后，我们只要返回 s[lps[-1]:][::-1] + s 即可，思想见思路1
beats 84.59%
class Solution(object):
def shortestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
pattern = s + '#' + s[::-1]
lps = self.findLPS(pattern)
return s[lps[-1]:][::-1] + s
def findLPS(self, pattern):
length, lps = 0, [0]
for i in range(1, len(pattern)):
while length > 0 and pattern[length] != pattern[i]:
length = lps[length - 1]
if pattern[length] == pattern[i]:
length += 1
lps.append(length)
return lps