214. Shortest Palindrome

beita 發布于2019-08-16 10:29 / 1560人閱讀

摘要：題目鏈接找到從頭開始最長的那么只要把的加到前面就是結果了。找的過程可以用來做優化，由于，那么就照著里面見數組的方法來查，最后就是的長度，注意兩個并在一起的要加分隔符，防止算的出問題。

214. Shortest Palindrome

題目鏈接：https://leetcode.com/problems...

找到string從頭開始最長的palindrome substring：s[0:i+1]
那么只要把substring(i+1)的reverse加到s前面就是結果了。
找palindrome substring的過程可以用kmp來做優化，由于reverse(s[0:i+1]) == s[0:i+1]，那么就照著kmp里面見prefix數組的方法來查，最后prefix[n-1]就是palindrome的長度，注意兩個string并在一起的要加分隔符，防止算prefix的出問題。

public class Solution {
    public String shortestPalindrome(String s) {
        StringBuilder rev = new StringBuilder(s).reverse();
        String d = s + "#" + rev.toString();
        int n = d.length();
        int[] prefix = new int[n];
        // i for rev, j for s
        int i = 1, j = 0;
        while(i < n) {
            // match
            if(d.charAt(j) == d.charAt(i)) {
                prefix[i] = j + 1;
                i++;  j++;
            }
            else {
                if(j == 0) i++;
                else j = prefix[j-1];
            }
        }
        
        StringBuilder sb = new StringBuilder();
        sb.append(s.substring(prefix[n-1]));
        return sb.reverse().append(s).toString();
    }
}

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

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

[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
Palindrome Pairs & Shortest Palindrome

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

CNZPH 2019-08-14 17:20 評論0 收藏0
[Leetcode] Shortest Palindrome 最短回文拼接法

摘要：第二個是，因為在第個位置，可以有最長為的相同前后綴，依次類推。匹配時分為幾種情況字母相同，則和都加，且，因為后綴匹配的長度是前綴的長度加。注意為了方便處理空字符串，我們在反轉拼接的時候中間加了，這個字符要保證不會出現在字符串中。 Shortest Palindrome Given a string S, you are allowed to convert it to a palin...

Chiclaim 2019-08-14 12:37 評論0 收藏0
前端 | 每天一個 LeetCode

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

張漢慶 2019-08-23 13:42 評論0 收藏0
leetcode 部分解答索引（持續更新～）

摘要：前言從開始寫相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫現在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖恪Ｋ栽谶@里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言從開始寫leetcode相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫～現在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個索引嘻嘻。順序整理 1~50 1...

leo108 2019-08-15 14:26 評論0 收藏0