C++ solution with priority queue


  • 0
    private:
        typedef pair<string, int> PSI;
        unordered_map<string, int> _hotDeg; // hot degree map
        string _s; // current typing sentence
        
    public:
        AutocompleteSystem(vector<string> sentences, vector<int> times) {
            for (int i = 0; i < times.size(); _hotDeg[sentences[i]] = times[i++]);
        }
        
        vector<string> input(char c) {
            if (c == '#') {
                _hotDeg[_s]++, _s.clear();
                return {};
            }
            
            _s += c;
            auto comp = [](const PSI& p1, const PSI& p2) { // true if p1 comes first
                return p1.second > p2.second || p1.second == p2.second && p1.first < p2.first;
            };
            priority_queue<PSI, vector<PSI>, decltype(comp)> q(comp);
            
            for (auto& p : _hotDeg)
                if (_s == p.first.substr(0, _s.size())) {
                  q.push(p);
                  if (q.size() > 3) q.pop();
                }
            
            vector<string> top3;
            while (!q.empty()) top3.push_back(q.top().first), q.pop();
            return reverse(top3.begin(), top3.end()), top3;
        }
    

Log in to reply
 

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