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