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

Chiclaim 發(fā)布于2019-08-14 12:37 / 1383人閱讀

摘要：第二個是，因為在第個位置，可以有最長為的相同前后綴，依次類推。匹配時分為幾種情況字母相同，則和都加，且，因為后綴匹配的長度是前綴的長度加。注意為了方便處理空字符串，我們在反轉拼接的時候中間加了，這個字符要保證不會出現(xiàn)在字符串中。

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算法的知識，可以先參考實現(xiàn)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，因為沒有區(qū)分前后綴。第二個a是1，因為在第2個位置，可以有最長為1的相同前后綴(a)，依次類推。這樣我們只要知道最后一個字母對應的數(shù)，就是這個字符串的最長公共前后綴長度了。那如何求這個表lps[]呢？我們用i表示其前綴的匹配位置，用j表示后綴的匹配位置。然后我們從i=1，j=0，i表示后綴匹配到的位置，j表示前綴匹配到得位置，開始依次向后尋找前綴和后綴的匹配情況。匹配時分為幾種情況：

字母相同，則i和j都加1，且lps[i] = j + 1，因為后綴匹配的長度是前綴的長度加1。前綴為j的已經(jīng)匹配了，現(xiàn)在多一個不就是再加1嗎。

字母不相同，且j還不是0時，可以將j回退至lps[j-1]，看看上一個子前綴到哪里結束的，從那里重新匹配。

如果字母不相同，且j是0，已經(jīng)無法回退，則說明lps[i]也是0了，根本無法匹配的意思，同時i也要加1，開始看下一個字母了。

這里情況2可能多次重復，直到進入了情況3。還不懂的可以看這個文章。

得到這個表后，我們把反轉字符串除去相應的后綴，然后加到前面就行了。

注意

為了方便處理空字符串，我們在反轉拼接的時候中間加了#，這個字符要保證不會出現(xiàn)在字符串中。

在計算表時，當前后綴指針指向字符相同時，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()){
            // 如果字母相等，則繼續(xù)匹配，最長相同前后綴的長度也加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++;
                }
            }
        }
    }
}

GPU云服務器云服務器 Shortest palindrome LeetCode LeetCode_String

文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64599.html

Palindrome Pairs & Shortest Palindrome

摘要：部分是回文的，在里面找是否有的。這里的范圍是，最小是，因為要保證是兩個單詞，最大是，這時候要找出另一個和他相反的串。判斷為回文，可以直接暴力，每個都判斷一次。兩個方向都找一遍就可能出現(xiàn)重復的情況，注意避免重復。例如，結果應該是。 Palindrome Pairs 鏈接：https://leetcode.com/problems... 這道題沒想出來思路，參考了這個博客的內容：http:...

CNZPH 2019-08-14 17:20 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網(wǎng)站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
LeetCode 336. Palindrome Pairs

摘要：描述給定一組唯一的單詞，找出所有不同的索引對，使得列表中的兩個單詞，，可拼接成回文串。遍歷每一個單詞，對每一個單詞進行切片，組成和。 Description Given a list of unique words, find all pairs of distinct indices (i, j) in the given list, so that the concatenatio...

TigerChain 2019-07-31 10:16 評論0 收藏0
javascript初探LeetCode之9.Palindrome Number

摘要：題目分析這是上的第題，難度為，判斷整型數(shù)字是否為回文串，需要注意兩點負數(shù)都不是回文小于的非負整數(shù)都是回文這一題與第題類似，也可以有兩種思路數(shù)組法和模十法。所以代碼可以如下改進能被整除的非整數(shù)和負數(shù)，返回題目 Determine whether an integer is a palindrome. Do this without extra space. 分析這是leetcode上...

icyfire 2019-08-21 16:58 評論0 收藏0
[LeetCode] 214. Shortest Palindrome

Problem 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. Exa...

liangdas 2019-08-16 13:56 評論0 收藏0