# I just change the solution of Trie!

• 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.