题目描述
给定一个字符串 s,你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
样例
示例1:
输入: "aacecaaa"
输出: "aaacecaaa"
示例2:
输入: "abcd"
输出: "dcbabcd"
算法1
(KMP) $O(n)$
暴力做法是逐次尝试添加字符,看是否能构成回文串,这里添加字符的顺序是从后往前开始,首先尝试添加末尾字符,然后尝试添加末两位字符等等,注意这里要逆序后添加。最多枚举$n$次,每次判断需要$O(n)$的复杂度,总时间复杂度为$O(n^2)$。
可以注意到如果添加 $k$ 个字符就能构成回文串,等价于字符串前 $n - k$ 个字符是回文的,所以问题转化为字符串从第一个字符开始,最长的回文子串是多少。这个可以利用KMP中的next
数组来求,回想到next[i]
等于以i
为结尾的字符串的最长公共前后缀的长度,注意这里前缀和后缀是不包含最后一个和第一个字符的,不然对每个字符串而言最长公共前后缀就是本身了。
我们可以将字符串逆序拼接到原字符串后形成的新字符串记为t
,长度设为m
,那么next[m]
就代表以m
为结尾的最长公共前后缀长度,相当于是原字符串的从第一个字符开始的最长回文子串。注意在拼接t
的时候要先在原字符串后添加一个不存在的字符,不然对于字符串aaaa
来说形成的t
串的 $next[m] = 2n - 1$,超过了原字符串的长度。
这里next[i]
中的i
代表着第 $i$ 个字符,下标是从1开始的,显然next[1] = 0
,因为只有一个字符的时候不存在前后缀,所以长度为0。而字符串的下标是从0开始的,为了方便处理,我们可以在字符串首加一个字符使得下标也从1开始。
而求next[i]
则可以利用递推的思想在 $O(n)$ 的时间对每个 $i$ 都求出来:假如已经求出了next[0],...,next[i - 1]
,我们令j = next[i - 1]
,然后我们先比较第 $i$ 个字符和第 $j + 1$ 个字符是否相等,如果相等那么next[i] = j + 1
并且更新j
,不然我们就利用next数组来不断的进行回退,即j = next[j]
。这里始终维护对于每个i
而言,j
是已经匹配的位置,j + 1
是将要匹配的位置。
C++ 代码
class Solution {
public:
string shortestPalindrome(string s) {
string t = " " + s + "#" + string(s.rbegin(), s.rend());
int n = t.size() - 1;
vector<int> ne(n + 1, 0);
for (int i = 2, j = 0; i <= n; i ++ ) {
while (j && t[i] != t[j + 1]) j = ne[j];
if (t[i] == t[j + 1]) j ++ ;
ne[i] = j;
}
string rev = s.substr(ne[n]);
reverse(rev.begin(), rev.end());
return rev + s;
}
};
算法2
(KMP) $O(n)$
这里也可以让next
和字符串的下标都从 $0$ 开始,不过j
变成了将要匹配的位置,j - 1
是已匹配的位置,所以回退的时候要用next[j - 1]
, next
数组的含义同样是下标以 $i$ 为结尾的字符串的最长公共前后缀长度,所以next[0] = 0
。这种写法对求next
数组的递推思想体现的更明显一些。
class Solution {
public:
string shortestPalindrome(string s) {
string t = s + "#" + string(s.rbegin(), s.rend());
int n = t.size();
vector<int> ne(n, 0);
for (int i = 1, j; i < n; i ++ ) {
j = ne[i - 1];
while (j && t[i] != t[j]) j = ne[j - 1];
if (t[i] == t[j]) j ++ ;
ne[i] = j;
}
string rev = s.substr(ne[n - 1]);
reverse(rev.begin(), rev.end());
return rev + s;
}
};