資訊專欄INFORMATION COLUMN
摘要：題目鏈接找到從頭開始最長的那么只要把的加到前面就是結(jié)果了。找的過程可以用來做優(yōu)化，由于，那么就照著里面見數(shù)組的方法來查，最后就是的長度，注意兩個(gè)并在一起的要加分隔符，防止算的出問題。
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的長度，注意兩個(gè)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)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/69888.html
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...
摘要：部分是回文的，在里面找是否有的。這里的范圍是，最小是，因?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:...
摘要：第二個(gè)是，因?yàn)樵诘趥€(gè)位置，可以有最長為的相同前后綴，依次類推。匹配時(shí)分為幾種情況字母相同，則和都加，且，因?yàn)楹缶Y匹配的長度是前綴的長度加。注意為了方便處理空字符串，我們?cè)诜崔D(zhuǎn)拼接的時(shí)候中間加了，這個(gè)字符要保證不會(huì)出現(xiàn)在字符串中。 Shortest Palindrome Given a string S, you are allowed to convert it to a palin...
摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...
摘要：前言從開始寫相關(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...
閱讀 929·2021-10-25 09:45
閱讀 3380·2021-09-22 14:58
閱讀 3962·2021-08-31 09:43
閱讀 982·2019-08-30 15:55
閱讀 983·2019-08-29 13:51
閱讀 1290·2019-08-29 13:02
閱讀 3548·2019-08-29 12:52
閱讀 2014·2019-08-26 13:27
