C++. using hash map.


  • 1
    H

    Hi , below is my solution using hash map , any idea why using hash map taking more time.
    Hashmap has query time = O(P) .

        class TrieNode {
        public:
            // Initialize your data structure here.
    // hash map with key as char and value as node .
            unordered_map<char , TrieNode*> children ;
            bool isleaf;
    // initialize them
            TrieNode():isleaf(false),children() {}
        };
        
        class Trie {
        public:
            Trie() {
                root = new TrieNode();
            }
            // Inserts a word into the trie.
            void insert(string word) {
                TrieNode *cur = root;
                for(int i = 0 ; i < word.size();i++){
    // if node is empty , create new node and  insert children map of parent.
                    if(cur->children.count(word[i])==0){
                        cur->children[word[i]] = new TrieNode();
                    }
                    cur = cur->children[word[i]];
                }
    // make the last node as leaf after whole pattern is scanned.
                cur->isleaf = true;
            }
        
            // Returns if the word is in the trie.
            bool search(string word) {
    // if node is not null and it is a leaf , we found the word else return false
                TrieNode *t = searchNode(word);
                if(t && t->isleaf)
                    return true;
                return false;
            }
        
            // Returns if there is any word in the trie
            // that starts with the given prefix.
            bool startsWith(string prefix) {
    // just find the word in the trie and return 
                if(searchNode(prefix))
                    return true;
                return false;
            }
        
            TrieNode *searchNode(string word){
                unordered_map<char , TrieNode*> children = root->children;
                TrieNode *t = NULL;
                for(int i = 0 ; i < word.size();i++){
    // if there is no node with particular char , the word does;t exits.return NULL
                    if(children.count(word[i])==0){
                        return NULL;
                    }
                    t = children[word[i]];
                    children = t->children;
                }
                return t;
            }
        private:
            TrieNode* root;
        };

  • 1
    J

    There is a implementation bug in gcc 4.7, see http://www.mail-archive.com/gcc-bugs@gcc.gnu.org/msg368044.html


Log in to reply
 

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