62ms (beats 99.33%) C++ Code using trie and DFS search


  • 0
    O

    The solution is easy to understand. Trie is used to store/search words. When wildcard '.' is in the string, do DFS search.

    class TrieNode {
    public:
        TrieNode* next[26];
        bool is_word;
        // Initialize your data structure here.
        TrieNode(): is_word(false) {
            memset(next, 0, sizeof(next));
        }
    };
    
    class WordDictionary {
    private:
        TrieNode* root;    
    public:
        WordDictionary() {
            root = new TrieNode();
        }
        // Adds a word into the data structure.
        void addWord(string word) {
            TrieNode* p = root;
            for(int i = 0; i < word.size(); i++) {
                if(p->next[word[i]-'a'] == NULL) {
                    p->next[word[i]-'a'] = new TrieNode();
                }
                p = p->next[word[i] - 'a'];
            }
            p->is_word = 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) {
            if(word.size() == 0) return true;       
            return search_rec(word, 0, root);
        }
    
    private:
        // DFS search  
        bool search_rec(string& word, int pos, TrieNode* p) {
            if(!p) return false;
            if(pos >= word.size()) return p->is_word;
            
            if(word[pos] == '.') {
                for(int i = 0; i < 26; i++) {
                    if(search_rec(word, pos+1, p->next[i]))
                        return true;
                }
                return false;
            } else {
                return search_rec(word, pos+1, p->next[word[pos] - 'a']);
            }
        }
    };
    

Log in to reply
 

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