84ms C++ solution, Depth-first-search


  • 7
    X
    class TrieNode {
    public:
        bool isComplete;
        TrieNode * ch[26];
        // Initialize your data structure here.
        TrieNode() {
            isComplete = false;
            for (int i = 0; i < 26; i++) ch[i] = NULL;
        }
    };
    
    class Trie {
    public:
        Trie() {
            root = new TrieNode();
        }
    
        // Inserts a word into the trie.
        void insert(string word) {
            // just insert one path from root node to the end
            TrieNode * p = root;
            for (auto c : word) {
                if (p->ch[c-'a'] == NULL) {
                    p->ch[c-'a'] = new TrieNode();
                }
                p = p->ch[c-'a'];
            }
            p->isComplete = true;
        }
    
        // Returns if the word is in the trie.
        bool search(string word) {
            return dfs(root, word, 0);
        }
        
        bool dfs(TrieNode* p, string& word, int startIndex) {
            if (p == NULL) return false;
            if (startIndex == word.length()) return p->isComplete;
            char c = word[startIndex];
            if (c == '.') {
                for (int i = 0; i < 26; i++) {
                    if (p->ch[i] != NULL) {
                        if (dfs(p->ch[i], word, startIndex + 1)) return true;
                    }
                }
                return false;
            } else {
                return dfs(p->ch[c - 'a'], word, startIndex + 1);
            }
        }
        
    private:
        TrieNode* root;
    };
    
    class WordDictionary {
        Trie trie;
    public:
    
        // Adds a word into the data structure.
        void addWord(string word) {
            trie.insert(word);
        }
    
        // 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 trie.search(word);
        }
        
    
    };

Log in to reply
 

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