问题描述
给到一个字符串，在字符串前面添加字符，可以使字符串形成回文字符串，要求找出最小的回文字符串。题目链接：**点我**
样例输入输出
输入：”aacecaaa”
输出：”aaacecaaa”
输入：”aa”
输出：”aa”
问题解法
解法一：双指针（超时）
使用首尾两个指针，如果首指针的字符不等于尾指针的字符，则尾指针向后移动首指针的长度，同时将尾指针的字符加到结果集中，然后将首指针恢复为0。如果首尾指针的字符相等，则首指针向右移动一位，尾指针向左移动一位。重复上述过程直到首尾指针相遇。代码如下
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
| class Solution
{
public String shortestPalindrome(String s)
{
StringBuilder sb = new StringBuilder();
int i = 0;
int j = s.length() - 1;
while (i < j)
{
if (s.charAt(i) == s.charAt(j))
{
i++;
j--;
}
else
{
j = j + i;
sb.append(s.charAt(j));
j--;
i = 0;
}
}
return sb.append(s).toString();
}
}
|
此解法虽然比较简单，但是超时了。
解法二：KMP（通过）
此解法参考：https://leetcode-cn.com/problems/shortest-palindrome/solution/zui-duan-hui-wen-chuan-by-leetcode-solution/。
要找最短的回文字符串，只需要在原有的字符串中找出最长的前缀回文字符串（比如：abaabaceaba 的最长前缀回文字符串是 abaaba），然后进行分割，将后半部分的字符串进行倒序加到原先字符串，即可得到最短的回文字符串。因此，此题就变成了查找字符串中的最长前缀回文字符串。更进一步，如果将原有字符串进行反序，然后将这两个字符串进行匹配，那么当反序的字符串遍历到结束时，原有字符串匹配到的位置进行分割，前面的字符串就是最长的前缀回文字符串。字符串的匹配过程中可以借助 KMP 算法的思想进行求解。代码如下
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
| class Solution
{
public String shortestPalindrome(String s)
{
if (s.length() == 0)
{
return s;
}
int[] next = new int[s.length()];
int point = 0;
for (int i = 1; i < s.length(); i++)
{
while (point > 0 && s.charAt(point) != s.charAt(i))
{
point = next[point - 1];
}
if (s.charAt(point) == s.charAt(i))
{
next[i] = point + 1;
point++;
}
}
int j = 0;
for (int i = s.length() - 1; i >= 0; i--)
{
while (j > 0 && s.charAt(i) != s.charAt(j))
{
j = next[j - 1];
}
if (s.charAt(i) == s.charAt(j))
{
j++;
}
}
StringBuilder sb = new StringBuilder();
if (j == 0)
{
sb.append(s.substring(j + 1));
}
else
{
sb.append(s.substring(j));
}
sb.reverse().append(s);
return sb.toString();
}
}
|
参考资料
https://leetcode-cn.com/problems/shortest-palindrome/solution/zui-duan-hui-wen-chuan-by-leetcode-solution/