Clean C++ solution using trie


  • 0
    A
    class WordDictionary {
    public:
        struct TrieNode {
            bool isWord;
            vector<TrieNode *> children;
            TrieNode() : isWord(false) {
                children.assign(26, NULL);
            }
        };
    
        /** Initialize your data structure here. */
        WordDictionary() {
            root = new TrieNode();
        }
        
        /** Adds a word into the data structure. */
        void addWord(string word) {
            TrieNode *curr = root;
            for (char c : word) {
                int i = c - 'a';
                if (!curr->children[i])
                    curr->children[i] = new TrieNode();
                curr = curr->children[i];
            }
            curr->isWord = true;
        }
        
        bool helper(TrieNode *node, string &word, int i) {
            if (i == word.length())
                return node->isWord;
            
            if (word[i] != '.') {
                auto child = node->children[word[i] - 'a'];
                return child && helper(child, word, i + 1);
            }
            
            for (auto child : node->children) {
                if (child && helper(child, word, i + 1))
                    return true;
            }
            return false;
        }
        
        /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
        bool search(string word) {
            return helper(root, word, 0);
        }
        
    private:
        TrieNode *root;
    };
    

Log in to reply
 

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