Re: [閒聊] 每日leetcode

看板Marginalman作者oin1104 (是oin的說)時間1年前 (2024/09/20 19:52)推噓5(5推 0噓 6→)

留言11則, 6人參與討論串885/1548 (看更多)

題目家最少的字符讓s變成回文思路把s翻轉之後用hash記每一種前綴然後用翻轉後的去找有對上的話就代表可以是回文但是這樣會炸記憶體所以失敗思路2 我用半個下午學了KMP 又機掰又詭異又複雜的演算法一樣是翻轉之後用原本的字串匹配翻轉後的字串因為是從後面來要注意一下然後用KMP來找找到底之後還剩下的字符就是需要加上去的字符太難了吧幹 class Solution { public: vector<int> next; int n ; void benext(string s) { int i = 0; int p = 1; while(p < n) { if(s[i] == s[p]) { i++; next[p] = i; p++; } else if (i == 0) { next[p] = 0; p++; } else { i = next[i-1]; } } } string shortestPalindrome(string s) { string rev = s ; reverse(rev.begin() , rev.end()); n = s.size(); next.resize(n,0); benext(s); int i = 0 ; int j = 0; while(i < n) { if(rev[i] == s[j]) { i++; j++; } else if(j>0) { j = next[j-1]; } else { i++; } if(j == n)break; } string res ; res = s; reverse(res.begin() , res.end()); for( ; j < n ; j ++) { res.push_back(s[j]); } return res; } }; -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.162.42 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1726833143.A.675.html

推

sustainer123

09/20 19:54, 1年前 , 1^F

09/20 19:54, 1^F

→

oin1104

09/20 19:54, 1年前 , 2^F

09/20 19:54, 2^F

推

Furina

09/20 19:56, 1年前 , 3^F

09/20 19:56, 3^F