Two ways of implementing Trie!


  • 0
    P

    first one:

    class TrieNode {
    public:
        // Initialize your data structure here.
        TrieNode(bool b = false) {
            isWord = b;
            memset(next, 0, sizeof(next));
        }
        bool isWord;    
        TrieNode *next[26];
    };
    
    class Trie {
    public:
        Trie() {
            root = new TrieNode();
        }
    
        // Inserts a word into the trie.
        void insert(string word) {
            TrieNode *node = root;
            for (auto c: word) {
                if (node->next[c-'a'] == nullptr)
                    node->next[c-'a'] = new TrieNode();
                node = node->next[c-'a'];
            }
            node->isWord = true;
        }
    
        // Returns if the word is in the trie.
        bool search(string word) {
            TrieNode *node = find(word);
            return node != nullptr && node->isWord;
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        bool startsWith(string prefix) {
            return find(prefix);
        }
    
    private:
        TrieNode* root;
        
        TrieNode* find(string &key) {
            TrieNode *node = root;
            for (auto c: key) {
                if (node->next[c-'a'] == nullptr)
                    return nullptr;
                node = node->next[c-'a'];
            }
            return node;
        }
    };
    

    second one:

    class TrieNode {
    public:
        // Initialize your data structure here.
        TrieNode(bool b = false) : val(0), isWord(b) {}
        TrieNode(char c, bool b = false) : val(c), isWord(b) {}
        
        TrieNode* findChild(char c) {
            for (auto child: children)
                if (child->val == c)
                    return child;
            return nullptr;
        }
        
        bool isWord;
        char val;
        vector<TrieNode *> children;
    };
    
    class Trie {
    public:
        Trie() {
            root = new TrieNode();
        }
    
        // Inserts a word into the trie.
        void insert(string word) {
            TrieNode *node = root;
            for (auto c: word) {
                TrieNode *child = node->findChild(c);
                if (child == nullptr) {
                    node->children.push_back(new TrieNode(c));
                    child = node->children.back();
                }
                node = child;
            }
            node->isWord = true;
        }
    
        // Returns if the word is in the trie.
        bool search(string word) {
            TrieNode *node = find(word);
            return node != nullptr && node->isWord;
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        bool startsWith(string prefix) {
            return find(prefix);
        }
    
    private:
        TrieNode* root;
        
        TrieNode* find(string &key) {
            TrieNode *node = root;
            for (auto c: key) {
                TrieNode *child = node->findChild(c);
                if (child == nullptr)
                    return nullptr;
                node = child;
            }
            return node;
        }
    };
    

    the first one is a little bit faster(56ms), while the second one(88ms)


Log in to reply
 

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