Design Add and Search Words Data Structure

Problem

Code editors and fuzzy search tools need to match patterns with wildcards against a dictionary of known words. Design a data structure that supports adding words and searching with patterns where '.' matches any single letter. The challenge is that wildcards require exploring multiple trie branches simultaneously.

add("bad"), add("dad"), add("mad")
search("pad")  → False
search(".ad")  → True   ('.' matches b, d, or m)
search("b..")  → True   ('b' then any two chars)
search("...")  → True   (any three chars)
search("....")  → False  (no 4-letter words)

Solution

Approach: Standard trie insert plus a recursive DFS that branches at every . wildcard.

add_word is an ordinary trie insert - walk the word, create missing nodes, mark is_end = True on the last one. All the difficulty is in search, which delegates to a recursive helper _search(node, index) carrying the current trie node and position in the pattern. The base case fires when index == len(word): the whole pattern has been consumed, so the answer is node.is_end - a real word must terminate exactly here. For a concrete character it behaves like a plain trie walk: if the character has no child, return False; otherwise recurse into node.children[char] at index + 1. The . case is what an iterative loop cannot express - the wildcard could match any present child, so it recurses into every child with any(_search(child, index + 1) for child in node.children.values()), returning True the moment one branch succeeds. Trace search("b..") with bad and bat inserted: match b exactly, then the first . recurses into the only child a, then the second . recurses into both d and t, and each is a complete word, so the search returns True.

Edge cases: A . at a node with no children makes the any(...) iterate an empty collection and return False. A pattern longer than any stored word fails because traversal runs out of children before the base case. Recursion always terminates since index strictly increases each call.

Complexity: O(m) time for add_word and for a wildcard-free search; worst case O(26^m * m) when the pattern is all dots, since each dot fans out to up to 26 children across m levels. O(total characters) space for the trie plus O(m) recursion depth.