• 21.1%

Design a data structure that supports the following two operations:

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

Note:
You may assume that all words are consist of lowercase letters a-z.

click to show hint.

You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first.

https://discuss.leetcode.com/topic/15581/80ms-clear-c-code-with-detailed-explanations

80ms Clear C++ Code with Detailed Explanations

This problem is an application of the Trie data structure. In the following, it is assumed that you have solved Implement Trie (Prefix Tree).

Now, let’s first look at the TrieNode class. I define it as follows.

The field isKey is to label whether the string comprised of characters starting from root to the current node is a key (word that has been added). In this problem, only lower-case letters a - z need to be considered, so each TrieNode has at most 26 children. I store it in an array of TrieNode*: children[i] corresponds to letter ‘a’ + i. The remaining code defines the constructor of the TrieNode class.

Adding a word can be done in the same way as in Implement Trie (Prefix Tree). The basic idea is to create a TrieNode corresponding to each letter in the word. When we are done, label the last node to be a key (set isKey = true). The code is as follows.

By the way, root is defined as private data of WordDictionary:

And the WordDictionary class has a constructor to initialize root:

Now we are left only with search. Let’s do it. The basic idea is still the same as typical search operations in a Trie. The critical part is how to deal with the dots .. Well, my solution is very naive in this place. Each time when we reach a ., just traverse all the children of the current node and recursively search the remaining substring in word starting from that children. So I define a helper function query for search that takes in a string and a starting node. And the initial call to query is like query(word, root).

By the way, I pass a char* instead of string to query and it greatly speeds up the code. So the initial call to query is actually query(word.c_str(), root).

Now I put all the codes together below. Hope it to be useful!

https://discuss.leetcode.com/topic/18578/c-using-trie-and-dfs-for-search-easy-understand-solution

C++ using Trie and DFS for search. easy understand solution

https://discuss.leetcode.com/topic/29809/python-168ms-beat-100-solution

Python 168ms-beat-100% solution

The search function could be done in a more pythonic way, but I see that performance has suffered so I just wrote the raw logic by myself.

https://discuss.leetcode.com/topic/14216/tree-solutions-18-20-lines

Tree solutions, 18-20 lines

An iterative alternative for the search method:

And one that’s a bit longer but faster:

And a neat version where I append my end-marker to the word to simplify the final check:

https://discuss.leetcode.com/topic/26944/python-solution-recursive-version-dfs

Python solution recursive version (DFS)