Two C++ O(n) Solutions: Array or Hashtable


  • 8
    L

    Edited: Finally, I solved the MLE problem and now I got two ways to deal with this problem.
    Editeded: Destructor added.

    Array:

    class TrieNode {
    public:
        // Initialize your data structure here.
        TrieNode(bool end=false) {
            memset(branches,0,sizeof(branches));
            isEnd=end;
        }
        TrieNode* branches[26];
        bool isEnd;
    };
    
    class Trie {
    public:
        Trie() {
            root = new TrieNode();
        }
    
        ~Trie() {
            destroy(root);
        }
        
        void destroy(TrieNode* node) {
            for(int i=0;i<26;i++)
                if(node->branches[i]) 
                    destroy(node->branches[i]);
            delete node;
        }
    
        // Inserts a word into the trie.
        void insert(string s) {
            TrieNode* node=root;
            int i;
            for(i=0;i<s.size();i++) {
                if(node->branches[s[i]-'a']==NULL)
                    break;
                else {
                    node=node->branches[s[i]-'a'];
                    node->isEnd=((i==s.size()-1)?true:node->isEnd);
                }
            }
            for(;i<s.size();i++) {
                node->branches[s[i]-'a']=new TrieNode(i==s.size()-1?true:false);
                node=node->branches[s[i]-'a'];
            }
        }
    
        // Returns if the word is in the trie.
        bool search(string key) {
            TrieNode* node=root;
            for(int i=0;i<key.size();i++)
                if(node->branches[key[i]-'a']==NULL)
                    return false;
                else
                    node=node->branches[key[i]-'a'];
            if(node->isEnd)
                return true;
            else
                return false;
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        bool startsWith(string prefix) {
            TrieNode* node=root;
            for(int i=0;i<prefix.size();i++)
                if(node->branches[prefix[i]-'a']==NULL)
                    return false;
                else
                    node=node->branches[prefix[i]-'a'];
            return true;
        }
    private:
        TrieNode* root;
    };
    

    Hashtable:

    class TrieNode {
    public:
        // Initialize your data structure here.
        TrieNode(bool end=false) {
            isEnd=end;
        }
        unordered_map<char,TrieNode*> branches;
        bool isEnd;
    };
    
    class Trie {
    public:
        Trie() {
            root = new TrieNode();
        }
        
        ~Trie() {
            destroy(root);
        }
    
        void destroy(TrieNode* node) {
            for(auto entry : node->branches)
                destroy(entry.second);
            delete node;
        }
    
        // Inserts a word into the trie.
        void insert(string s) {
            TrieNode* node=root;
            int i;
            for(i=0;i<s.size();i++) {
                if(node->branches.find(s[i])==node->branches.end())
                    break;
                else {
                    node=node->branches[s[i]];
                    node->isEnd=((i==s.size()-1)?true:node->isEnd);
                }
            }
            for(;i<s.size();i++) {
                node->branches[s[i]]=new TrieNode(i==s.size()-1?true:false);
                node=node->branches[s[i]];
            }
        }
    
        // Returns if the word is in the trie.
        bool search(string key) {
            TrieNode* node=root;
            for(int i=0;i<key.size();i++)
                if(node->branches.find(key[i])==node->branches.end())
                    return false;
                else
                    node=node->branches[key[i]];
            if(node->isEnd)
                return true;
            else
                return false;
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        bool startsWith(string prefix) {
            TrieNode* node=root;
            for(int i=0;i<prefix.size();i++)
                //if(node->branches[prefix[i]]==NULL)
                if(node->branches.find(prefix[i])==node->branches.end())
                    return false;
                else
                    node=node->branches[prefix[i]];
            return true;
        }
    private:
        TrieNode* root;
    };

  • 0
    C

    You can use an unordered_map to implement the node structure.


  • 1
    Y

    Use map or unordered_map to replace your branches vector. But what surprised me is that using these two data structures will slow down the algorithm. In fact, your algorithm is not correct. For insert("ab"), insert("acb"), search("ac"), the output should be false but your solution seems to return true.
    I think the test case is not good. Easy to cause MLE. In most cases, we use vector<TreeNode *> branches(26) for fast query. But here this solution will cause MLE.


  • 0
    L

    Are you sure? My implementation will set isEnd only for the last char of a word, so in the case of insert("ab"), insert("acb"), search("ac"), only the node contains 'b' got its isEnd set. So it will return false for "ac".


  • 0
    L

    Did you try unordered_map? I tried it first, but got MLE.


  • 0
    L

    But should implement destructor ?


  • 0
    L

    Yep, I should. I added the destructor now. Thank you!


Log in to reply
 

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