[LeetCode] Shortest Palindrome 最短回文串

0
0
0
1. 云栖社区>
2. 博客>
3. 正文

## [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;
}
}```

+ 关注