[LeetCode] 214. Shortest Palindrome

liangdas 發(fā)布于2019-08-16 13:56 / 2150人閱讀

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.

Example 1:

Input: "aacecaaa"
Output: "aaacecaaa"
Example 2:

Input: "abcd"
Output: "dcbabcd"

Solution

class Solution {
    public String shortestPalindrome(String s) {
        int len = s.length();
        int i = len;
        for (i = len; i >= 0; i--) {
            if (isPalindrome(s.substring(0, i))) break;
        }
        StringBuilder sb = new StringBuilder();
        
        if (i < 0) {
            sb.append(s).reverse();
            return sb.toString()+s;
        }
        
        sb.append(s.substring(i)).reverse();
        return sb.toString() + s;
    }
    private boolean isPalindrome(String s) {
        int i = 0, j = s.length()-1;
        while (i <= j) {
            if (s.charAt(i++) != s.charAt(j--)) return false;
        }
        return true;
    }
}

云服務(wù)器 GPU云服務(wù)器 Shortest palindrome LeetCode LeetCode_String

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

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

相關(guān)文章

214. Shortest Palindrome

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

beita 2019-08-16 10:29 評論0 收藏0
[Leetcode] Shortest Palindrome 最短回文拼接法

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

Chiclaim 2019-08-14 12:37 評論0 收藏0
Palindrome Pairs & Shortest Palindrome

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

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

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

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

摘要：前言從開始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)懍F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖恪Ｋ栽谶@里做個(gè)索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言從開始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)憽F(xiàn)在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個(gè)索引嘻嘻。順序整理 1~50 1...

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