# [LeetCode] 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.

For example:

Given "aacecaaa", return "aaacecaaa".

Given "abcd", return "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) {
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;
}
}

C++ 解法二：

class Solution {
public:
string shortestPalindrome(string s) {
string t = s;
reverse(t.begin(), t.end());
int n = s.size(), i = 0;
for (i = n; i >= 0; --i) {
if (s.substr(0, i) == t.substr(n - i)) {
break;
}
}
return t.substr(0, n - i) + 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;
}
}

|
8月前
|
Python
LeetCode 234. 回文链表 Palindrome Linked List
LeetCode 234. 回文链表 Palindrome Linked List
31 0
|
8月前
LeetCode 409. Longest Palindrome

43 0
|
8月前
|

LeetCode 336. Palindrome Pairs

60 0
|
8月前
|

LeetCode 214. Shortest Palindrome

31 0
|
8月前
|
canal
LeetCode 125. Valid Palindrome

47 0
【LeetCode】Palindrome Pairs（336）
Given a list of unique words. Find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a 　　palindrome.
58 0
LeetCode之Palindrome Number（回文数）
LeetCode之Palindrome Number（回文数）
47 0
|
Java Python