[Leetcode] Shortest Palindrome 最短回文拼接法
文章目录
Shortest Palindrome
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算法
复杂度
时间 O(logN) 空间 O(H)
思路
这题要用到部分KMP算法的知识,可以先参考实现StrStr这篇文章。
这题的技巧性非常强,我们观察一下abb这个字符串,将其反转后得到bba,如果只是想得到回文串,那把这个反转的字符串放在前面得到bbaabb就肯定是了。但这明显不是最长的,我们再展示一个技巧,将该反转字符串放在后面再观察一下abbbba,它的前缀和后缀的情况有这些:
a a
ab ba
abb bba
abbb bbba
... ...
显然,这个合并的字符串长度最长的相同前后缀是a,这时候我们把反转后的字符串bba中最后那个a去掉,得到bb,这时候再把bb接到原字符串前面,得到bbabb,这就是最短的回文拼接方法了!
再用一个例子,比如aaba,翻转后得到abaa,然后拼接起来得到aabaabaa,其最长公共前后缀是aa,去掉这个后缀的反转字符串是ab,再接到原字符串上就是abaaba,即最短的回文拼接。
那如何求这个最长公共前后缀有多长呢?这里就要借用KMP算法中的partial match table了,对于刚才的aaba,其连接后为aabaabaa,它的表是:
a a b a a b a a
0 1 0 1 2 3 1 2
第一个a是0,因为没有区分前后缀。第二个a是1,因为在第2个位置,可以有最长为1的相同前后缀(a),依次类推。这样我们只要知道最后一个字母对应的数,就是这个字符串的最长公共前后缀长度了。那如何求这个表lps[]呢?我们用i表示其前缀的匹配位置,用j表示后缀的匹配位置。然后我们从i=1,j=0,i表示后缀匹配到的位置,j表示前缀匹配到得位置,开始依次向后寻找前缀和后缀的匹配情况。匹配时分为几种情况:
字母相同,则i和j都加1,且
lps[i] = j + 1,因为后缀匹配的长度是前缀的长度加1。前缀为j的已经匹配了,现在多一个不就是再加1吗。字母不相同,且j还不是0时,可以将j回退至
lps[j-1],看看上一个子前缀到哪里结束的,从那里重新匹配。如果字母不相同,且j是0,已经无法回退,则说明
lps[i]也是0了,根本无法匹配的意思,同时i也要加1,开始看下一个字母了。
这里情况2可能多次重复,直到进入了情况3。还不懂的可以看这个文章。
得到这个表后,我们把反转字符串除去相应的后缀,然后加到前面就行了。
注意
为了方便处理空字符串,我们在反转拼接的时候中间加了
#,这个字符要保证不会出现在字符串中。在计算表时,当前后缀指针指向字符相同时,
lps[i] = j + 1而不是lps[i] = lps[i - 1] + 1; 当j退回0时,lps[i] = 0;
代码
public class Solution {
public String shortestPalindrome(String s) {
// 将字符串反转后拼接到后面
String rev = (new StringBuilder(s)).reverse().toString();
String combine = s + "#" + rev;
// 计算LPS表值
int[] lps = new int[combine.length()];
getLPS(combine, lps);
int remove = lps[lps.length-1];
// 去掉后缀后,将反转字符串拼回前面
String prepend = rev.substring(0, rev.length() - remove);
return prepend + s;
}
private void getLPS(String s, int[] lps){
// i是后缀末尾的指针,j是前缀末尾的指针
int j = 0, i = 1;
lps[0] = 0;
// 从j=0,i=1开始找,错开了一位
while(i < s.length()){
// 如果字母相等,则继续匹配,最长相同前后缀的长度也加1
if(s.charAt(i) == s.charAt(j)){
lps[i] = j + 1;
i++;
j++;
// 如果不同
} else {
// 如果前缀末尾指针还没退回0点,则找上一个子前缀的末尾位置
if(j != 0){
j = lps[j - 1];
// 如果退回0点,则最长相同前后缀的长度就是0了
} else {
lps[i] = 0;
i++;
}
}
}
}
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论