Clear C++ solution using vector


  • 0
    
    class TrieTreeNode {
    public:
        vector<TrieTreeNode*> child;
        bool isLeaf;
        
        TrieTreeNode(){
            child.resize(LETTERS, NULL);
            isLeaf = false;
        }
    };
    
    class WordDictionary {
    public:
        WordDictionary(){
            root = new TrieTreeNode();
        }
        
        // Adds a word into the data structure.
        void addWord(string word) {
            TrieTreeNode* curr = root;
            for (int i=0;i<word.size();i++){
                if (curr->child[word[i] - 'a'] == NULL)
                    curr->child[word[i] - 'a'] = new TrieTreeNode();
                curr = curr->child[word[i] - 'a'];
            }
            curr->isLeaf = true;
        }
    
        // 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 find(word, root);
        }
        
    private:
        TrieTreeNode* root;
        
        bool find(string word, TrieTreeNode* head){
            TrieTreeNode* curr = head;
            for (int i=0;curr && i<word.size();i++){
                if (word[i] == '.'){
                    for (int j=0;j<26;j++){
                        TrieTreeNode* tmp = curr;
                        tmp = tmp->child[j];
                        if (find(word.substr(i+1), tmp))
                            return true;
                    }
                    return false;
                }else {
                    curr = curr->child[word[i]-'a'];
                }
            }
            
            return curr && curr->isLeaf;
        }
    };
    
    // Your WordDictionary object will be instantiated and called as such:
    // WordDictionary wordDictionary;
    // wordDictionary.addWord("word");
    // wordDictionary.search("pattern");
    

Log in to reply
 

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