推 Lilchicken: 大帥 09/25 22:17
推 dont: 大師 09/25 23:22
這一整周都打算練習trie是吧
題目: 2416. Sum of Prefix Scores of Strings
給你一個字串vector，求每一個其中字串的所有prefix出現在全部字串的全部prefix次
數和vector
思路:
照做，先用全部字串建一次trie，每造訪到trie節點該節點的count就+1，建完後全部
字串走一次trie把所有該字串經過節點遇到的count總和後存回vector。複雜度O(n*m)，
排名前面的做法應該是先將字串sort過後求兩兩相鄰的prefix長度後減少之後第二次跑trie
需要的次數，但速度快上許多 蠻神奇的，一般做法比較靠背的是會吃MLE(用vector)
class trie{
public:
trie* t[26]={};
int cnt=0;
};
class Solution {
public:
vector<int> sumPrefixScores(vector<string>& words) {
trie* pre_ans= new trie();
vector<int> ans;
for(auto k:words){
trie* temp=pre_ans;
for(auto j:k){
if(!temp->t[j-'a']){
temp->t[j-'a']=new trie();
}
temp->t[j-'a']->cnt++;
temp=temp->t[j-'a'];
}
}
for(auto k:words){
trie* temp=pre_ans;
int cur=0;
for(auto j:k){
cur+=temp->t[j-'a']->cnt;
temp=temp->t[j-'a'];
}
ans.push_back(cur);
}
return ans;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.227.252.3 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1727273745.A.D93.html