Simple Trie without extra classes


  • 1

    Just use the Trie as Trie node:

    class Trie {
    public:
        bool end = false;
        vector<Trie*> next = vector<Trie*>(26, NULL);
    
        /** Initialize your data structure here. */
        Trie() {}
    
        /** Inserts a word into the trie. */
        void insert(string word) {
            Trie* ptr = this;
            for (auto c : word) {
                c -= 'a';
                ptr = ptr->next[c] 
                    ? ptr->next[c] 
                    : ptr->next[c] = new Trie();
            }
            ptr->end = true;
        }
        
        /** Returns if the word is in the trie. */
        bool search(string word) {
            Trie* ptr = traverse(word);
            return ptr ? ptr->end : false;
        }
        
        /** Returns if there is any word in the trie that starts with the given prefix. */
        bool startsWith(string prefix) {
            Trie* ptr = traverse(prefix);
            return ptr;
        }
    
    private:
        Trie* traverse(string& word) {
            Trie* ptr = this;
            for (auto c : word) {
                c -= 'a';
                if (!ptr->next[c]) return NULL;
                ptr = ptr->next[c];
            }
            return ptr;
        }
    };
    

  • 0

    Even shorter version:

    class Trie {
    public:
        bool end = false;
        vector<Trie*> next = vector<Trie*>(26, NULL);
    
        void insert(string word) {
            Trie* ptr = this;
            for (auto c : word) ptr = ptr->next[c -= 'a'] ? ptr->next[c] : ptr->next[c] = new Trie();
            ptr->end = true;
        }
        
        bool search(string word) {
            return traverse(word) == 2;
        }
        
        bool startsWith(string prefix) {
            return traverse(prefix);
        }
    
    private:
        // returns 0 if word is not in the trie, 1 if word is prefix of a word in the trie and 2 if word is in the trie
        int traverse(string& word) {
            Trie* ptr = this;
            for (auto c : word) {
                if (!ptr->next[c -= 'a']) return 0;
                ptr = ptr->next[c];
            }
            return ptr->end + 1;
        }
    };
    

Log in to reply
 

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