DFS and Trie

• Trie + DFS

Time Complexity:
search O(26 ^ len(word))

Submission Runtime 145ms

Make use of lc208 Implement Trie. First define a TrieNode struct, is_word is very important to indicate current node is end the of a word or not.

``````    struct TrieNode {
bool is_word;
TrieNode* children[26];
TrieNode (bool word=false) {
memset(children, 0, sizeof(children));
is_word = word;
}
};

WordDictionary() {
root = new TrieNode();
}
``````

addWord is as same as lc208

``````/** Adds a word into the data structure. */
TrieNode* node = root;
for (int i = 0; i < word.size(); i++) {
if (node->children[word[i] - 'a'] == nullptr) {
node->children[word[i] - 'a'] = new TrieNode();
}
node = node->children[word[i] - 'a'];
}

node->is_word = true;
}
``````

the trivial part is how to deal with '.' . This indicates we should explore all possibilities when running into a '.'. Here DFS + backtracking saves the day.

The recursion function defines whether we can find substring word[pos, last] in node-rooted subtree.

``````/** 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 find(word, 0, root);
}

bool find(string word, int pos, TrieNode* node) {
if (pos == word.size()) {
return node->is_word;
}

if (word[pos] != '.') {
if (node->children[word[pos] - 'a']) {
return find(word, pos + 1, node->children[word[pos] - 'a']);
}
} else {
for (int i = 0; i < 26; i++) {
if (node->children[i] != nullptr &&
find(word, pos + 1, node->children[i]))
return true;
}
}

return false;
}
``````

One of my question is why my solution is so slow. I think time complexity is just like what I mentioned before when using trie. Anyone can point out optimization . Thanks a lot

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