Keshawn_lu's Blog

Leetcode 214. 最短回文串

字数统计: 525阅读时长: 2 min
2020/08/29 Share

题目简介:

给定一个字符串 s,你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

示例 1:

1
2
输入: "aacecaaa"
输出: "aaacecaaa"

示例 2:

1
2
输入: "abcd"
输出: "dcbabcd"

思路:

第一次尝试用KMP方法做题,有点头疼。

我们记s的逆转字符串为reverse_str,其实题目可以转换为s前缀和reverse_str后缀的最长公共部分,如下图所示:

这时我们可以将模式串定义为s + # + reverse_str(#用来分割),将这个字符串的最长公共前后缀找到即可。

寻找最长公共前后缀的方法就要用到KMP了,我们需要求出next数组,具体方法如下:

  1. 定义一个k来表示之前的最长公共前后缀
  2. pattern[i - 1] == pattern[k],则说明该字符也匹配到了,最长公共前后缀+1,next[i] = k + 1
  3. pattern[i - 1] != pattern[k] && k == 0,则说明没有匹配的前后缀,next[i] = 0
  4. pattern[i - 1] != pattern[k] && k != 0,则我们需要找字符串pattern[0 ... k]中的公共前后缀的长度,即k = next[k]

找出模式串的最长公共前后缀后,返回reverse_str.substr(0, reverse_str.size() - max_common) + s即可(即加上的字符串为逆转字符串的前缀)。

代码如下:

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

int kmp_next(string& pattern){

vector<int> next(pattern.size() + 1, 0);

int k = 0; //记录之前的最长公共前后缀

next[0] = -1;
next[1] = 0; //一个字母没有前后缀

int i = 2;
while(i < next.size()){ //pattern索引比next数组索引小1

if(pattern[i - 1] == pattern[k]){

next[i] = k + 1; //之前的前后缀长度+1
k = next[i];
i++;
}
else if(k == 0){

next[i] = 0;
i++;
}
else{

k = next[k];
}
}

return next[next.size() - 1]; //返回该字符串的最长公共前后缀
}


string shortestPalindrome(string s) {

string reverse_str = s;

reverse(reverse_str.begin(), reverse_str.end()); //逆转字符串

string pattern = s + '#' + reverse_str;

int max_common = kmp_next(pattern);

return reverse_str.substr(0, reverse_str.size() - max_common) + s;

}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: