# 214. Shortest Palindrome

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"

Credits:
Special thanks to @ifanchu for adding this problem and creating all test cases. Thanks to @Freezen for additional test cases.

C++ 解法一：

class Solution {
public:
string shortestPalindrome(string s) {
int i = 0, n = s.size();
for (int j = n - 1; j >= 0; --j) {
if (s[i] == s[j]) ++i;
}
if (i == n) return s;
string rem = s.substr(i);
reverse(rem.begin(), rem.end());
return rem + shortestPalindrome(s.substr(0, i)) + s.substr(i);
}
};

Java 解法一：

public class Solution {
public String shortestPalindrome(String s) {
int i = 0, n = s.length();
for (int j = n - 1; j >= 0; --j) {
if (s.charAt(i) == s.charAt(j)) ++i;
}
if (i == n) return s;
String rem = s.substring(i);
String rem_rev = new StringBuilder(rem).reverse().toString();
return rem_rev + shortestPalindrome(s.substring(0, i)) + rem;
}
}

C++ 解法二：

class Solution {
public:
string shortestPalindrome(string s) {
string r = s;
reverse(r.begin(), r.end());
string t = s + "#" + r;
vector<int> next(t.size(), 0);
for (int i = 1; i < t.size(); ++i) {
int j = next[i - 1];
while (j > 0 && t[i] != t[j]) j = next[j - 1];
next[i] = (j += t[i] == t[j]);
}
return r.substr(0, s.size() - next.back()) + s;
}
};

Java 解法二：

public class Solution {
public String shortestPalindrome(String s) {
String r = new StringBuilder(s).reverse().toString();
String t = s + "#" + r;
int[] next = new int[t.length()];
for (int i = 1; i < t.length(); ++i) {
int j = next[i - 1];
while (j > 0 && t.charAt(i) != t.charAt(j)) j = next[j - 1];
j += (t.charAt(i) == t.charAt(j)) ? 1 : 0;
next[i] = j;
}
return r.substring(0, s.length() - next[t.length() - 1]) + s;
}
}

Java 解法三：

public class Solution {
public String shortestPalindrome(String s) {
int i = 0, end = s.length() - 1, j = end;
char arr = s.toCharArray();
while (i < j) {
if (arr[i] == arr[j]) {
++i; --j;
} else {
i = 0; --end; j = end;
}
}
return new StringBuilder(s.substring(end + 1)).reverse().toString() + s;
}
}

Github 同步地址：

https://github.com/grandyang/leetcode/issues/214

Longest Palindromic Subsequence

Implement strStr()

https://leetcode.com/problems/shortest-palindrome/

https://leetcode.com/problems/shortest-palindrome/discuss/60098/My-7-lines-recursive-Java-solution

https://leetcode.com/problems/shortest-palindrome/discuss/60113/Clean-KMP-solution-with-super-detailed-explanation

https://leetcode.com/problems/shortest-palindrome/discuss/60106/My-9-lines-three-pointers-Java-solution-with-explanation

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation