AC C++ solution using unordered_map for next


  • 0
    N

    This implementation uses unordered_map for next.

    class TrieNode {
    public:
        bool is_word;
        unordered_map<char, TrieNode*> next;
        // Initialize your data structure here.
        TrieNode() : is_word(false), next() { }
    };
    
    class Trie {
    public:
        Trie() {
            root = new TrieNode();
        }
        
        // Free resources
        ~Trie() {
            destroy(root);
        }
    
        // Inserts a word into the trie.
        void insert(const string& s) {
            TrieNode* node = root;
            for (auto c: s) {
                if (node->next.count(c) == 0) node->next[c] = new TrieNode();
                node = node->next[c];
            }
            node->is_word = true;
        }
    
        // Returns if the word is in the trie.
        bool search(const string& key) {
            TrieNode* node = getNode(key);
            return node != nullptr && node->is_word;
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        bool startsWith(const string& prefix) {
            return getNode(prefix) != nullptr;
        }
        
        // Return the node if the key exists in the trie, nullptr otherwise
        TrieNode* getNode(const string& key) {
            TrieNode* node = root;
            for (auto c: key) {
                if (node->next.count(c) == 0) return nullptr;
                node = node->next[c];
            }
            return node;
        }
    
    private:
        TrieNode* root;
        
        // Free recources in post order
        void destroy(TrieNode* root) {
        	for (auto node : root->next) {
        		destroy(node.second);
        	}
    	    delete root;
        }
    };
    
    // Your Trie object will be instantiated and called as such:
    // Trie trie;
    // trie.insert("somestring");
    // trie.search("key");

  • 0
    J

    You could just use an array of 128 instead of the un_orederedmap


Log in to reply
 

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