C++ Trie and DFS solution beats 80%

  • 1

    Match the prefix using a Trie and do a DFS to find all the competing strings and put them in a priority queue. Initially I created a map of (string, count) at each TrieNode but it's very inefficient as far as memory's concerned. Also, I search the trie from the previous character encountered and reset the starting TrieNode for new input sequence.

    class AutocompleteSystem {
        class TrieNode{
                unordered_map<char, TrieNode*> child;
                string str;
                int count;
                TrieNode(): str(""), count(0) {}
        void insert(string& s, TrieNode* root, int times){
            TrieNode* curr = root;
            for (int i=0;i<s.size();i++){
                if (!curr->child.count(s[i]))
                    curr->child[s[i]] = new TrieNode();
                curr = curr->child[s[i]];
            curr->count += times;
            curr->str = s;
        void dfs(TrieNode* temp){
            if (temp->str != "") q.push({temp->str, temp->count});
            for (auto& ele: temp->child){
        struct comp{
            bool operator() (pair<string, int>& a, pair<string, int>& b){
                return a.second<b.second || a.second==b.second && a.first>b.first;
        priority_queue<pair<string, int>, vector<pair<string, int> >, comp> q;
        TrieNode* root, *curr;
        AutocompleteSystem(vector<string> sentences, vector<int> times) {
            root = new TrieNode();
            for (int i=0;i<sentences.size();i++){
                insert(sentences[i], root, times[i]);
            curr = root;
        string s="";
        vector<string> input(char c) {
            q = priority_queue<pair<string, int>, vector<pair<string, int> >, comp>();
            if (c=='#'){
                insert(s, root, 1);
                curr = root; //start searching from the beginning node for the next sentence
                return {};
            s += c;
            if (curr && curr->child.count(c)){
                curr = curr->child[c];
                curr = NULL; //curr node is null so empty result for any further characters in current input 
                return {};
            if (curr->str != "") q.push({curr->str, curr->count});
            for (auto& ele: curr->child){
            vector<string> res;
            while (!q.empty() && res.size()<3){
            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.