Why unordered_map solution slower then map solution??


  • 0
    D
    class TrieNode {
    public:
        // Initialize your data structure here.
        bool leaf;
        unordered_map<char, TrieNode *>  next;
        TrieNode() { leaf = false;   }
    };
    
    class Trie {
    public:
        Trie() {
            root = new TrieNode();
        }
        
        char get(char x) { return x; }
    
        
        void insert(string word) {
            TrieNode * cur = root;
            int id = 0;
            while (id <= word.size()) {
                if (id == word.size()) cur->leaf = true;
                else
                if (cur->next[get(word[id])]) 
                    cur = cur->next[get(word[id])];
                else
                break;
                id++;
            }
            while (id <= word.size()) {
                if (id == word.size()) cur->leaf = true;
                else {
                    TrieNode * nextNode = new TrieNode();
                    cur->next[get(word[id])] = nextNode;
                    cur = nextNode;
                }
                id++;
            }
        }
    
     
        bool search(string word) {
            TrieNode * cur = root;
            int id = 0;
            while (id <= word.size()) {
                if (id == word.size()) {
                    return cur->leaf;
                }
                if (id < word.size() && cur && cur->next[get(word[id])]) {
                    cur = cur->next[get(word[id])];
                    id++;
                }
                else
                return false;
            }
        }
       
        bool startsWith(string prefix) {
           
            TrieNode * cur = root;
            int id = 0;
            while (id <= prefix.size()) {
                if (!cur) return false;
                cur = cur->next[get(prefix[id])];
                id++;
            }
        
            return true;
        }
    
    private:
        TrieNode* root;
    };
    
    // Your Trie object will be instantiated and called as such:
    // Trie trie;
    // trie.insert("somestring");
    // trie.search("key");

Log in to reply
 

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