国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

214. Shortest Palindrome

beita / 1561人閱讀

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

214. Shortest Palindrome

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

找到string從頭開始最長的palindrome substring：s[0:i+1]
那么只要把substring(i+1)的reverse加到s前面就是結(jié)果了。
找palindrome substring的過程可以用kmp來做優(yōu)化，由于reverse(s[0:i+1]) == s[0:i+1]，那么就照著kmp里面見prefix數(shù)組的方法來查，最后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();
    }
}

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

轉(zhuǎn)載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/69888.html

相關(guān)文章

  • [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 評論0 收藏0

  • Palindrome Pairs & Shortest Palindrome

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

    CNZPH 評論0 收藏0

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

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

    Chiclaim 評論0 收藏0

  • 前端 | 每天一個 LeetCode

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

    張漢慶 評論0 收藏0

  • leetcode 部分解答索引（持續(xù)更新～）

    摘要：前言從開始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時也沒有按順序?qū)懍F(xiàn)在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時也沒有按順序?qū)憽F(xiàn)在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。 順序整理 1~50 1...

    leo108 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<