C++ Trie Tree ,beats 85%


  • 0
    B
    struct TrieNode{
        TrieNode *next[26];
        bool isWord;
        TrieNode(){
            for(int i = 0;i<26;i++) next[i] = NULL;
            isWord = false;
        }
    };
    class WordDictionary {
    private:
        TrieNode* root;
    public:
        /** Initialize your data structure here. */
        WordDictionary() {
            root = new TrieNode();
        }
        
        /** Adds a word into the data structure. */
        void addWord(string word) {
            TrieNode* tmp = root;
            for(int i = 0;i < word.size();i++){
                int id = word[i] - 'a';
                if(tmp->next[id] == NULL){
                    tmp->next[id] = new TrieNode();
                }
                tmp = tmp->next[id];
            }
            tmp->isWord = 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 search_rec(root,word,0);
        }
        bool search_rec(TrieNode* root,const string & word,int idx){
            for(;idx < word.size();idx++){
                if(word[idx] == '.'){
                    for(int i = 0;i<26;i++){
                        if(root->next[i] && search_rec(root->next[i],word,idx + 1)) return true;
                    }
                    return false;
                }else{
                    root = root->next[word[idx] - 'a'];
                    if(!root) return false;
                }
            }
            if(idx == word.size()) return root->isWord;
            return false;
        }
    };
    
    /**
     * Your WordDictionary object will be instantiated and called as such:
     * WordDictionary obj = new WordDictionary();
     * obj.addWord(word);
     * bool param_2 = obj.search(word);
     */

Log in to reply
 

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