Re: [閒聊] 每日leetcode
214.
最短帕林捉 :
給你一個字串
從頭加字進去 讓他變成帕林捉
回傳最短的那種
==================== ======
絲路：
嗎的原本9.要去睡了
想說看一下今天daily
嗎呀怎麼是hard
還給不給人睡ㄚ
============== == ========
真的思路：
扣掉從頭開始的最大回文
剩下的翻過來加到頭上
kmp掃到一半
逆向回來找
長度剛好跟剩下的字數一樣的話
就找到最大回文
剩下的就內褲套頭
class Solution {
public:
string shortestPalindrome(string s) {
int len = s.length();
int half = len / 2 + 1;
//KMP half from s[0] to s[half]
vector<int> dp;
dp.push_back(0);
int idx = 0;
for(int i = 1; i < half; i++){
while(idx != 0 and s[i] != s[idx]){
idx = dp[idx-1];
}
if(s[i] == s[idx]){
idx++;
}
dp.push_back(idx);
}
idx = 0;
string res;
for(int i = len - 1; i >= 0; i--){
while(idx != 0 and s[i] != s[idx]){
idx = dp[idx-1];
}
if(s[i] == s[idx]) idx++;
if(idx == i){
string t = s.substr(i*2);
reverse(t.begin(), t.end());
res = t + s;
break;
}
else if(idx == i+1){
string t = s.substr(i*2 + 1);
reverse(t.begin(), t.end());
res = t + s;
break;
}
}
return res;
}
};
- -
簡單來說就是把內褲脫下來套在頭上
https://i.imgur.com/Yv4iPJr.jpeg
-----
Sent from JPTT on my iPad
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.205.121.194 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1726796208.A.85A.html
※ 編輯: sixB (123.205.121.194 臺灣), 09/20/2024 09:38:30
推
09/20 09:42,
1年前
, 1F
09/20 09:42, 1F
推
09/20 09:52,
1年前
, 2F
09/20 09:52, 2F
→
09/20 10:22,
1年前
, 3F
09/20 10:22, 3F
推
09/20 11:28,
1年前
, 4F
09/20 11:28, 4F
討論串 (同標題文章)
完整討論串 (本文為第 883 之 1548 篇)：