给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
示例 1:
输入: “aacecaaa”
输出: “aaacecaaa”
示例 2:
输入: “abcd”
输出: “dcbabcd”
题解
可利用Manacher 算法找到原字符串包含第一个字符的最长回文子串，将该回文子串后的字符逆序加到开头即可。
示例 1 中，对 aacecaaa 来说，包含第一个字符的最长回文子串为 aacecaa ，需把剩余的 a 逆序加到开头，即得到 aaacecaaa ；示例 2 中，abcd 包含第一个字符的最长回文子串为 a ，bcd 逆序得到 dcb ，放到开头即得到 dcbabcd 。
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| public class ShortestPalindrome {
public static String preprocess(String s) {
String result = "^";
for (int i = 0; i < s.length(); i++) {
result += "#" + s.charAt(i);
}
return result + "#$";
}
public static String shortestPalindrome(String s) {
if (s == null || s.length() == 0) return "";
String tmpStr = preprocess(s);
int strLen = tmpStr.length();
int C = 0, R = 0;
int[] p = new int[strLen];
int maxLen = 0;
for (int i = 1; i < strLen - 1; i++) {
p[i] = R > i ? Math.min(p[2 * C - i], R - i) : 1;
while (tmpStr.charAt(i - p[i]) == tmpStr.charAt(i + p[i])) {
p[i]++;
}
if (R < p[i] + i) {
R = p[i] + i;
C = i;
}
if (maxLen < p[i] - 1 && (C - p[C]) / 2 == 0) {
maxLen = p[i] - 1;
}
}
String result = "";
for (int i = s.length() - 1; i >= maxLen; i--) {
result += s.charAt(i);
}
return result + s;
}
}
|
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class ShortestPalindrome:
def shortest_palindrome(self, s: str) -> str:
tmp_str = "^#" + "".join([x + "#" for x in s]) + "$"
str_len = len(tmp_str)
p = [0] * str_len
c, r = 0, 0
max_len = 0
for i in range(1, str_len - 1):
p[i] = min(p[2 * c - i], r - i) if r > i else 1
while tmp_str[i - p[i]] == tmp_str[i + p[i]]:
p[i] += 1
if r < p[i] + i:
r = p[i] + i
c = i
if max_len < p[i] - 1 and (c - p[c]) // 2 == 0:
max_len = p[i] - 1
return "".join([x for x in s[:max_len - 1:-1]]) + s
|
Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| func preprocess(s string) string {
result := "^#"
for _, ch := range s {
result += string(ch) + "#"
}
return result + "$"
}
func shortestPalindrome(s string) string {
if len(s) == 0 {
return ""
}
tmpStr := preprocess(s)
strLen := len(tmpStr)
p := make([]int, strLen)
C, R := 0, 0
maxLen := 0
for i := 1; i < strLen-1; i++ {
if R > i {
p[i] = min(p[2*C-i], R-i)
} else {
p[i] = 1
}
for tmpStr[i-p[i]] == tmpStr[i+p[i]] {
p[i]++
}
if R < p[i]+i {
R = p[i] + i
C = i
}
if maxLen < p[i]-1 && (C-p[C])/2 == 0 {
maxLen = p[i] - 1
}
}
result := ""
for i := len(s) - 1; i >= maxLen; i-- {
result += string(s[i])
}
return result + s
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
|