※ 引述《dont (dont)》之銘言：
: 2416. Sum of Prefix Scores of Strings
: ## 思路
嗎的怎麼又是trie==
試試hash好了撞到
check collision然後就tle
然後trie child 開vector會MLE
超靠杯==
又學到一招
然後看solution n^2的比trie(nk)還快
好神奇
// trie n*k 569ms
class Trie{
public:
Trie* child[26] = {};
int cnt = 0;
};
class Solution {
public:
Trie* root = new Trie();
vector<int> sumPrefixScores(vector<string>& words) {
for(string& s: words){
Trie* cur = root;
for(char& c: s){
int idx = c - 'a';
if(cur->child[idx] == nullptr)
cur->child[idx] = new Trie();
cur->child[idx]->cnt++;
cur = cur->child[idx];
}
}
vector<int> res;
for(string& s: words){
Trie* cur = root;
int sum = 0;
for(char& c: s){
int idx = c - 'a';
cur = cur->child[idx];
sum += cur->cnt;
}
res.push_back(sum);
}
return res;
}
};
//////////////
// sort, adj prefix O(n^2) 110ms
class Solution {
public:
vector<int> sumPrefixScores(vector<string>& words) {
int n = words.size();
vector<pair<string, int>> words2;
for (int i = 0; i < n; ++i) {
words2.push_back(make_pair(words[i], i));
}
sort(words2.begin(), words2.end());
vector<int> commonPrefix(n);
for (int i = 1; i < n; ++i) {
string const& w1 = words2[i - 1].first;
string const& w2 = words2[i].first;
int l = min(w1.size(), w2.size());
int p = 0;
while (p < l && w1[p] == w2[p]) {
++p;
}
commonPrefix[i] = p;
}
vector<int> ret(n);
for (int i = 0; i < n; ++i) {
int prefix = words2[i].first.size();
ret[words2[i].second] += prefix;
for (int j = i + 1; j < n; ++j) {
prefix = min(prefix, commonPrefix[j]);
if (prefix == 0) {
break;
}
ret[words2[i].second] += prefix;
ret[words2[j].second] += prefix;
}
}
return ret;
}
};