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.

Example 1:

Input():
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["tan"],["man"],["fun"],["ran"],["tan"],[".an"],["f.."]]
Output: [null,null,null,null,false,true,true,true]
Explanation: "ran" was never added, "tan" matches exactly, and "." matches any single letter.

Example 2:

add("tan"), add("man"), add("fun")
search("....")
Output: False
Explanation: no 4-letter words were inserted, so the 4-character pattern cannot match.

Constraints:

• word in addWord consists of lowercase English letters.
• word in search consists of '.' or lowercase English letters.
• There will be at most 3 dots in word for search queries.
• At most 5000 calls will be made to addWord and search.
• 1 <= word.length <= 20

Solution Breakdown

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("t..") with tan and tin inserted: match t exactly, then the first . recurses into the only child a, then the second . recurses into both n and i, 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.