I just change the solution of Trie!


  • 0
    P

    I think it's pretty easy to understand. If we see a '.', and there exists some char in the tree, if it's the last one and is marked as end of word, return true, or we use the next node to start a new search(use stack to consider all possibilities!)

    class TrieNode {
    
    public:
        TrieNode(bool b = false) {
            isWord = b;
            memset(next, 0, sizeof(next));
        }
        bool isWord;    
        TrieNode *next[26];
    };
    
    class Trie {
    public:
        Trie() {
            root = new TrieNode();
        }
    
        void insert(string word) {
            TrieNode *node = root;
            for (auto c: word) {
                if (node->next[c-'a'] == nullptr)
                    node->next[c-'a'] = new TrieNode();
                node = node->next[c-'a'];
            }
            node->isWord = true;
        }
        
        bool search(string word, TrieNode *node) {
            for (int i = 0;i < word.size();++i) {
                char c = word[i];
                if (c == '.') {
                    for (int j = 0;j < 26;++j)
                        if (node->next[j])
                            if (i == word.size()-1 && node->next[j]->isWord || search(word.substr(i+1),node->next[j]))
                                return true;
                    return false;
                } else if (node->next[c-'a'] == nullptr)
                    return false;
                node = node->next[c-'a'];
            }
            return node != nullptr && node->isWord;
        }
        
        bool search(string word) {
            return search(word, root);
        }
    
    private:
        TrieNode* root;
    };
    
    
    class WordDictionary {
    private:
        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.