leetcode Shortest Palindrome(最短回文)分析和题解

将原字符串变成回文的最简单方法就是将原字符串反转后连在原字符串的前面,但是这种方法得到的回文未必是最短的回文。如果反转后的字符串末尾与原字符串的前端若干个字符是完全相同的,便可以通过首尾相连缩短回文的长度。这种“字符串末尾与原字符串前端字符“的表达其实就是后缀和前缀的关系,因此本文使用KMP算法解决leetcode上的最短回文(Shortest Palindrome)问题!

最短回文问题Shortest Palindrome的leetcode描述如下:

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”.

将原来的字符串变成回文的最简单方法就是将原字符串反转后连在原字符串的前面

如下图所示,将原字符串反转后连在原字符串前面形成回文。

最短回文算法

但是这种方法得到的回文未必是最短的回文。比如上图所示例子

如果反转后的字符串末尾与原字符串的前端若干个字符是相等的,就可以缩短回文的长度!!

这里提到的“字符串末尾与原字符串前端字符”一看就是后缀和前缀的关系。。。。

因此,可以使用KMP算法啊!!!

具体C++代码如下:

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
// C++
class Solution {
public:

void getNext(const string &s, vector<int> &next)
{

int len = -1;
int j = 0;
next[0] = -1;

while(j < s.length())
{
if(len == -1 || s[j] == s[len])
{
len ++;
j ++;
next[j] = len;
}
else
{
len = next[len];
}
}
}

string shortestPalindrome(string s) {
if(s.length() <= 1)
return s;

string reverseS = s;
reverse(reverseS.begin(), reverseS.end());

string str = s + "#" + reverseS; // 加#是为了避免在aaaaa这种情况下,得到的next为aaaaaaaaaa

vector<int> next(str.length()+1, 0);

getNext(str, next);

int maxLen = next[str.length()];

string result;
result = reverseS.substr(0, s.length()-maxLen) + s;

return result;
}
};