Design Search Autocomplete System.cpp

struct Node
{
    vector<pair<int, string>> sentences;
    unordered_map<char, Node*> children;
};

class AutocompleteSystem {
public:
    AutocompleteSystem(vector<string> sentences, vector<int> times) {
        root = new Node();
        int len = sentences.size();
        for(int i = 0; i < len; ++i)
            insert(sentences[i], times[i]);
        curr = root;
    }
    
    ~AutocompleteSystem()
    {
        del(root);
    }
    
    vector<string> input(char c) {
        if(c == '#')
        {
            curr = root;
            insert(typed, 1);
            typed = "";
            return {};
        }
        typed += c;
        if(!curr)return {};
        //don't use curr = curr->children[c] and check if curr is nullptr
        //that will add {c, nullptr} to the children map
        if(curr->children.find(c) == curr->children.end())
        {
            curr = nullptr;
            return {};
        }
        curr = curr->children[c];
        int len = curr->sentences.size();
        vector<string> res;
        for(int i = 0; i < min(3, len); ++i)
            res.push_back(curr->sentences[i].second);
        return res;
    }
    
private:
    Node* root, *curr;
    string typed;
    
    void insert(const string& sentence, int time)
    {
        int len = sentence.size();
        Node* curr = root;
        for(int i = 0; i < len; ++i)
        {
            char c = sentence[i];
            if(curr->children.find(c) == curr->children.end())
                curr->children[c] = new Node();
            update(curr, sentence, time);
            curr = curr->children[c];
        }
        //update terminal node
        update(curr, sentence, time);
    }
    
    void del(Node* curr)
    {
        if(!curr)return;
        for(auto& pair : curr->children)
            del(pair.second);
        delete curr;
    }
    
    void update(Node* curr, const string& sentence, int time)
    {
        if(curr == root)return;
        auto iter = find_if(curr->sentences.begin(), curr->sentences.end(), [sentence](const pair<int, string>& entry)
                            {
                                return entry.second == sentence;
                            });
        if(iter != curr->sentences.end())
            ++iter->first;
        else
            curr->sentences.emplace_back(time, sentence);
        auto comp = [](const pair<int, string>& lhs, const pair<int, string>& rhs)
        {
            return lhs.first == rhs.first? lhs.second < rhs.second : lhs.first > rhs.first;
        };
        sort(curr->sentences.begin(), curr->sentences.end(), comp);
    }
};

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