[642. Design Search Autocomplete System] C++ Priority Queue and Trie


  • 0
    class compare{
    public:
    bool operator()(pair<string, int> a, pair<string, int> b){
        return a.second < b.second || (a.second == b.second && a.first > b.first);
    }
    };
    
    class tnode{
    public:
    tnode(){}
    unordered_map<char, tnode*> child;
    priority_queue<pair<string, int>, vector<pair<string,int> > , compare> pq;
    };
    
    class AutocompleteSystem {
    public:
    tnode* root = new tnode();
    tnode* ptr = root;
    string istr = "";
    unordered_map<string, int> mp;//string, times
    void addstr(string& s, tnode* root, int time){
        tnode* r = root;
        for(int j = 0; j < s.size(); ++j){
            if(r->child.find(s[j]) == r->child.end()){
                r->child[s[j]] = new tnode();
            }
            r->child[s[j]]->pq.push({s, time});
            r = r->child[s[j]];
        }
    }
    
    void UpdateTree(tnode* root, string& s){
        tnode* r = root;
        for(int i = 0; i < s.size(); ++i){
            vector<pair<string, int> > tmp;
            while(!r->child[s[i]]->pq.empty()){
                auto m = r->child[s[i]]->pq.top();
                r->child[s[i]]->pq.pop();
                if(m.first == s){m.second++; tmp.push_back(m); break;}
                else{tmp.push_back(m);}
            }
            while(!tmp.empty()){
                r->child[s[i]]->pq.push(tmp.back());
                tmp.pop_back();
            }
            r = r->child[s[i]];
        }
    }
    
    AutocompleteSystem(vector<string> sentences, vector<int> times) {
        for(int i = 0; i < sentences.size(); ++i){
            mp[sentences[i]] = times[i];
            addstr(sentences[i], root, times[i]);
        }
    }
    
    vector<string> input(char c) {
        vector<string> res;
        if(c == '#'){
            if(mp.find(istr) == mp.end()){
                addstr(istr, root, 1);
                mp[istr] = 0;
            }else{
                UpdateTree(root, istr);
            }
            mp[istr]++;
            ptr = root;
            istr = "";
        }else{
            istr += c;
            if(ptr == nullptr || ptr->child.find(c) == ptr->child.end()){
                ptr = nullptr;
            }else{
                vector<pair<string, int> > tmp;
                while(!ptr->child[c]->pq.empty() && res.size() < 3){
                    auto m = ptr->child[c]->pq.top();
                    ptr->child[c]->pq.pop();
                    res.push_back(m.first);
                    tmp.push_back(m);
                }
                while(!tmp.empty()){
                    ptr->child[c]->pq.push(tmp.back());
                    tmp.pop_back();
                }
            }
        }
        return res;
    }
    };
    

    /**

    • Your AutocompleteSystem object will be instantiated and called as such:
    • AutocompleteSystem obj = new AutocompleteSystem(sentences, times);
    • vector<string> param_1 = obj.input(c);
      */

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.