214. Shortest Palindrome 最短回文串

@TOC

# 题目描述

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"
``````

# 解题方法

# 前缀是否回文

``````class Solution:
def shortestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if len(s) > 40000: return 'a' * 20000 + "dc" + s
N = len(s)
for i in range(N, -1, -1):
if self.isPalindrome(s[:i]):
return s[i:][::-1] + s
return ""

def isPalindrome(self, s):
N = len(s)
for i in range(N // 2):
if s[i] != s[N - i - 1]:
return False
return True
``````

# 判断前缀

``````s:       (aacecaa)a
t:      a(aacecaa)
a aacecaaa
``````

``````class Solution:
def shortestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
N = len(s)
if N == 0: return ""
t = s[::-1]
for i in range(N, 0, -1):
if s[:i] == t[N - i:]:
break
return t[:N - i] + s
``````