Design Add and Search Words Data Structure
Design Add and Search Words Data Structure: design a dictionary that stores words and searches patterns where . can stand for any single letter.
- 1 <= word.length <= 25
- word in addWord consists of lowercase English letters.
- word in search consist of '.' or lowercase English letters.
- There will be at most 2 dots in word for search queries.
- At most 10⁴ calls will be made to addWord and search.
Intuition
Design add and search words data structure builds a dictionary supporting insertion and a search where . matches any single character. Without the wildcard this is an ordinary trie; the wildcard is what makes it interesting.
Insertion is standard — walk the trie from the root, creating nodes as needed, and mark the final node as terminating a word.
Searching splits into two cases at each character:
- A concrete letter follows exactly one child; a . must try every child, since any could lead to a match.
That second case forces the search to branch, which means a simple loop is no longer sufficient. Recursion (or an explicit stack) is required, because a wildcard can succeed down one child and fail down another, and failure must return to try the remaining ones.
The recursive search takes a node and a position in the word. On a letter, descend into that child if it exists, or return false. On a ., try the search from every existing child, returning true if any succeeds.
The base case is reaching the end of the word: return whether the current node is marked as a word ending. Returning true merely for arriving at a valid node is the classic bug — it makes searching for "ap" succeed when only "apple" was inserted, because the path exists without terminating a word.
Worst case, a search of all dots visits every node, giving O(26^m) in principle but far less in practice, since only existing children are explored rather than all 26 possibilities.
Repeated word insertion plus prefix-shaped lookup is a strong trie signal. When one pattern symbol can match any single character, keep normal trie traversal for fixed letters and use DFS only at wildcard positions.
Approach
Before reading on: price up what the direct approach costs here, then ask what the shared prefixes let you avoid storing twice. Aim for O(L) for add; O(26^L) worst-case for search time and O(total inserted characters) space.
Build a standard trie
Each node holds children keyed by character and a flag marking a word ending. Without the wildcard this is an ordinary prefix tree, and insertion never changes.
Insert by walking and creating
Descend from the root, creating missing child nodes, then mark the final node as terminating a word. Insertion cost is proportional to the word length.
Follow a concrete letter directly
On a normal character, descend into that single child if it exists, or return false. This is the ordinary trie lookup path.
Branch on a wildcard
A . must try every existing child, since any could lead to a match. This branching is why the search must recurse — a failure down one child has to return and try the rest.
Check the word-ending flag
At the end of the word, return whether the node is marked as terminating. Returning true just for reaching a valid node makes "ap" match when only "apple" was added.
Explore only existing children
Iterate the children that exist rather than all 26 letters. The theoretical worst case is O(26^m), but real dictionaries explore a small fraction of that.
Cost of the operations
Insertion is O(m) for a word of length m. Search is O(m) with no wildcards, degrading toward O(26^m) as dots dominate. Space is O(total characters inserted).
Solution & live demo
Common pitfalls
Treating the wildcard as a literal key
node = node.children[ch]
for child in node.children.values():
A dot represents every available character at that depth. Looking up a child named . misses every valid wildcard match.
Accepting any consumed path as a word
return True
return node.is_word
Consuming the pattern may stop at a non-terminal prefix. The dictionary should match only words that were actually added.
Restarting after choosing a wildcard child
if dfs(self.root, index + 1):
if dfs(child, index + 1):
Once a wildcard chooses a character, the rest of the pattern must continue below that child. Restarting at the root combines pieces from unrelated words.
Edge cases
...The DFS explores trie paths of exactly three characters and accepts only a terminal node, so it matches a stored three-letter word but not a longer word sharing that prefix.
app after adding appleTraversal reaches the node for the prefix, but its terminal flag is false, so the search correctly returns false.
The insertion follows the existing path and sets the same terminal flag again, leaving search behaviour unchanged.