My 72ms C++ trie solution, beat 98.35%.


  • 0
    M
    class TrieNode {
    public:
        // Initialize your data structure here.
        bool exist;
        TrieNode *next[26];
        TrieNode():exist(false) {
            fill_n(next,26,nullptr);
        }
    };
    class WordDictionary {
    private:
        TrieNode* root;
        bool search(string& word,TrieNode *node,int pos){
            if(!node)return false;
            for(int i=pos;i<word.length();++i){
                if(word[i]=='.'){
                    for(int j=0;j<26;++j)
                        if(search(word,node->next[j],i+1))return true;
                    return false;
                }
                int j=word[i]-'a';
                if(!node->next[j])return false;
                node=node->next[j];
            }
            return node->exist;
        }
    public:
        WordDictionary(){
            root = new TrieNode();
        }
    
        // Adds a word into the data structure.
        void addWord(string word) {
            TrieNode *node=root;
            for(int i=0;i<word.length();++i){
                int j=word[i]-'a';
                if(!node->next[j])
                    node->next[j]=new TrieNode();
                node=node->next[j];
            }
            node->exist=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(word,root,0);
        }
    };
    
    // 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.