2022秋招备战!每天写至少一篇Leetcode里Hard难度题目的题解
214. 最短回文串
给定一个字符串 s,你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
示例 1:
输入:s = "aacecaaa"
输出:"aaacecaaa"
示例 2:
输入:s = "abcd"
输出:"dcbabcd"
提示:
0 <= s.length <= 5 * 104
s
仅由小写英文字母组成
本题的题意很简单,在一个现存的字符串前面添加一个前缀,使得整个字符串变成一个回文串。
再进行简单分析,假设即将添加的回文字符串为P, 原字符串为S。那么可以知道,如果想要S+P为回文串,S的后缀,假设为P’,必定和P形成回文串。剩下的中间部分也一定是回文串。
题意可以转化为,我们想找到S里,一个最大回文串X。因为当X作为一个回文串最大的时候,P’必定最小,同时P也会最小。形成的S + P也必定最小。因为X是回文串,P’和P也会形成回文关系,最终的S+P也会是回文串。
将S反转,构造出S’。因为X’是是X的反转,现在问题再次转化为KMP中的求前后缀相等数量的问题,即为求next数组。这里的#符号,用来保证了X的合法性,因为构造出来的X永远不会越过#符号。
接下来就是背代码的时间了。
构建next数组的代码模板,来自Y总。从1开始比较好写。
auto buildNext = [&] (){
for(int i = 2, j = 0; i < m; i++) {
while(j && s[i] != s[j + 1]) j = next[j];
if (s[i] == s[j + 1]) j++;
next[i] = j;
}
};
全部代码
class Solution {
public:
string shortestPalindrome(string s) {
int n = s.size();
if (n == 0) return "";
string tmp = s;
string copy = string(s.rbegin(), s.rend());
s = ' ' + s + '#' + copy; // kmp下标从1开始比较好写
int m = s.size();
vector<int> next(m);
auto buildNext = [&] (){
for(int i = 2, j = 0; i < m; i++) {
while(j && s[i] != s[j + 1]) j = next[j];
if (s[i] == s[j + 1]) j++;
next[i] = j;
}
};
buildNext();
int maxLen = next.back();
assert(maxLen >= 1);
string p = tmp.substr(maxLen);
string res = string(p.rbegin(), p.rend()) + tmp;
return res;
}
};