96ms C++ solution


  • 0
    I

    Could probably make it a bit faster by maintaining an ordered list of child nodes.

    class TrieNode {
    public:
        string letter;
        std::vector<TrieNode*> next;
    
        // Initialize your data structure here.
        TrieNode() {
            letter = "";
            next = {};
        }
        
        TrieNode* find(char c) {
            for(int i = 0; i < next.size(); i++)
            {
                if (next[i]->letter[0] == c)
                    return next[i];
            }
            return NULL;
        }
        
    };
    
    class Trie {
    public:
        Trie() {
            root = new TrieNode();
        }
    
        // Inserts a word into the trie.
        void insert(string word) {
            TrieNode* node = root;
            for(int i = 0; i < word.length(); i++)
            {
                TrieNode* nextNode = node->find(word[i]);
            
                if(!nextNode)
                {
                    TrieNode* newNode =  new TrieNode();
                    newNode->letter = word[i];
                    node->next.push_back(newNode);
                    nextNode = newNode;
                }
                
                node = nextNode;
            }
            
            TrieNode* newNode =  new TrieNode();
            newNode->letter = '\0';
            node->next.push_back(newNode);
        }
    
        // Returns if the word is in the trie.
        bool search(string word) {
            TrieNode* node = root;
            for(int i = 0; i < word.length(); i++)
            {
                TrieNode* nextNode = node->find(word[i]);
                if(!nextNode)
                    return false;
                node = nextNode;
            }
            
            TrieNode* finalNode = node->find('\0');
            if(finalNode)
                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.length(); i++)
            {
                TrieNode* nextNode = node->find(prefix[i]);
                if(!nextNode)
                    return false;
                node = nextNode;
            }
            return true;
        }
    
    private:
        TrieNode* root;
    };
    
    // Your Trie object will be instantiated and called as such:
    // Trie trie;
    // trie.insert("somestring");
    // trie.search("key");

  • 0
    T

    I define TrieNode class as below:
    TrieNode{
    bool exist;
    unordered_map<char, TrieNode*> word_map;
    TrieNode(){
    exist = false;
    word_map={};
    }
    }
    this takes 160ms.


Log in to reply
 

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