C++ 62ms 25 lines using Trie and DFS


  • 0
    class WordDictionary {
    private:
        class TrieNode {
        public:
            bool isWord = false;
            TrieNode* children[26];
            TrieNode() { memset(children, NULL, sizeof(children)); }
        };
        
        TrieNode* root = new TrieNode();
        
        bool mySearch(string& word, int start, TrieNode* cur) {
            if (start == word.length()) { return cur->isWord; }
            if (word[start] == '.') {
                for (TrieNode* next : cur->children) { 
                    if (next && mySearch(word, start + 1, next)) { return true; } 
                }
                return false; 
            }
            return cur->children[word[start] - 'a'] && mySearch(word, start + 1, cur->children[word[start] - 'a']);
        }
        
    public:
        void addWord(string word) {
            TrieNode* cur = root;
            for (int i = 0; i < word.length(); i++) {
                int idx = word[i] - 'a';
                if (!cur->children[idx]) { cur->children[idx] = new TrieNode(); }
                cur = cur->children[idx];
            }
            cur->isWord = true;
        }
    
        bool search(string word) {
            return mySearch(word, 0, root);
        }
    };
    

Log in to reply
 

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