A trie solution from modified trie implementation


  • 0
    S
    class TrieNode {
    public:
    vector<TrieNode *> next;// pointers to 26 different subtree
    bool exist;             // indentify whether the node construct a word
    
    // Initialize your data structure here.
    TrieNode() {
        next = vector<TrieNode *>(26, NULL);
        exist = false;
    }
    };
    
    class WordDictionary {
    public:
    WordDictionary() {
        root = new TrieNode();
    }
    
    // Inserts a word into the trie tree.
    void addWord(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->exist = true;
    }
    
    // Returns if the word (or a regular expression string) is in the trie tree.
    bool search(string word) {
        return isearch(root, word);
    }
    
    // a  ->  a
    // a  ->  a.
    // ab ->  a. ("." is the last character, then jumps to check node "b" whether exist)
    // NUL->  .
    bool isearch(TrieNode* iroot, string word) {
        TrieNode *node = iroot;
        for (int i = 0; i < word.size(); ++i) {
            if (word[i] == '.') {
                for (TrieNode *n : node->next) {
                    // only not NULL sub trie can continue to check
                    if (n && isearch(n, word.substr(i+1)) ) return true;
                }
                return false;
            }
            else {
                int id = word[i] - 'a';
                node = node->next[id];
                if (node == NULL) return false;
            }
        }
        return node->exist;
    }
    
    private:
    TrieNode* root;
    };

Log in to reply
 

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