Re: [閒聊] 每日leetcode

[sixB (6B)]

※ 引述《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;
                }
        };
-----
Sent from JPTT on my iPad

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.205.121.194 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1727256724.A.E72.html
推 DJYOSHITAKA: 別捲了 拜託你
→ sixB: 都trie幾天了==根本都一樣