C++ Trie solution; 62 ms ; defeat 93.96%


  • 0
    Y
    struct TrieNode {
        bool isValid = false;
        TrieNode* next[26] = {NULL};
    };
    class WordDictionary {
    public:
    
        // Adds a word into the data structure.
        void addWord(string word) {
            TrieNode* current = ≜
            for (auto& u : word) {
                int index = u - 'a';
                if (!current->next[index]) current->next[index] = new TrieNode();
                current = current->next[index];
            }
            current->isValid = true;
        }
    
        // Returns if the word is in the data structure. A word could
        // contain the dot character '.' to represent any one letter.
        bool search(const string& word, int offset, TrieNode* current) {
            if (offset == word.size()) return current ? current->isValid : false;
            if (current == NULL) return false;
            if (word[offset] == '.') {
                for (int i = 0; i < 26; ++i)
                    if (search(word, offset + 1, current->next[i])) return true;
                return false;
            } else {
                return search(word, offset + 1, current->next[word[offset] - 'a']);
            }
        }
        bool search(string word) {
            return search(word, 0, &trie);
        }
        TrieNode trie;
    };
    
    // 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.