[Leetcode] Shortest Palindrome 最短回文拼接法

java 3 2016-02-29 13:03
女装

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表示前缀匹配到得位置,开始依次向后寻找前缀和后缀的匹配情况。匹配时分为几种情况:

  1. 字母相同,则i和j都加1,且lps[i] = j + 1,因为后缀匹配的长度是前缀的长度加1。前缀为j的已经匹配了,现在多一个不就是再加1吗。

  2. 字母不相同,且j还不是0时,可以将j回退至lps[j-1],看看上一个子前缀到哪里结束的,从那里重新匹配。

  3. 如果字母不相同,且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++;
                }
            }
        }
    }
}
女装
文章评论