Share my C++ Implementation


  • 0
    N
    class TrieNode {
    private:
        const int kCharSetSize = {26};
        bool is_word; // word flag
        vector<TrieNode*> children; // 26 children
    
    public:
        // Initialize your data structure here.
        TrieNode() : is_word(false), children(kCharSetSize, nullptr) { }
        
        // Returns the child point to by the letter c whose index is c - 'a'
        TrieNode* getChild(char c) const {
            return  children[c-'a'];
        }
        
        // Inserts the child of the letter c
        void putChild(char c) {
            children[c-'a'] = new TrieNode();
        }
        
        // returns true if it is a word, false otherwise
        bool isWord() const {
            return is_word;
        }
        
        // Sets the word
        void setWord() {
            is_word = true;
        }
    };
    
    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->getChild(c) == nullptr){
                    node->putChild(c);
                } 
                node = node->getChild(c);
            }
            node->setWord();
        }
    
        // Returns if the word is in the trie.
        bool search(const string& key) {
            TrieNode* node = find(key);
            return node != nullptr && node->isWord();
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        bool startsWith(const string& prefix) {
            return find(prefix) != nullptr;
        }
        
        // Return the node if the key exists in the trie, nullptr otherwise
        TrieNode* find(const string& key) {
            TrieNode* node = root;
            for (auto c: key) {
                node = node->getChild(c);
                if (node == nullptr) return nullptr;
            }
            return node;
        }
    
    private:
        TrieNode* root;
        
        // Free resources in post order
        void destroy(TrieNode* root) {
        	for (char c = 'a'; c <= 'z'; ++c) {
        		if (root->getChild(c)) destroy(root->getChild(c));
        	}
    	    delete root;
        }
    };
    
    // Your Trie object will be instantiated and called as such:
    // Trie trie;
    // trie.insert("somestring");
    // trie.search("key");

  • 0
    W

    how long is your run time? I'm trying to find better solution with less than 60ms. Thanks.


Log in to reply
 

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