A very clean and standard solution for trie implementation


  • -1
    S
    //
    class TrieNode {
    public:
        int count;              // prefix words exist count
        vector<TrieNode *> next;// pointers to 26 different subtree
        bool exist;             // indentify whether the node construct a word
    
        // Initialize your data structure here.
        TrieNode() {
            count = 0;
            next = vector<TrieNode *>(26, NULL);
            exist = false;
        }
    };
    
    class Trie {
    public:
        Trie() {
            root = new TrieNode();
        }
    
    // Inserts a word into the trie.
    void insert(string word) {
        TrieNode *node = root;
        int id = 0;
        for (char c : word) {
            id = c - 'a';
            if (node->next[id] == NULL) node->next[id] = new TrieNode();
            node = node->next[id];
            ++node->count;
        }
        node->exist = true;
    }
    
    // Returns if the word is in the trie.
    bool search(string word) {
        TrieNode *node = root;
        int id = 0;
        for (char c : word) {
            id = c - 'a';
            node = node->next[id];
            if (node == NULL) return false;
        }
        return node->exist;
    }
    
    // Returns if there is any word in the trie
    // that starts with the given prefix.
    bool startsWith(string prefix) {
        TrieNode *node = root;
        int id = 0;
        for (char c : prefix) {
            id = c - 'a';
            node = node->next[id];
            if (node == NULL) return false;
        }
        
        return node->count > 0;
    }
    
    private:
        TrieNode* root;
    };

Log in to reply
 

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