Implement the data structure with wildcard support. Core ideas:
addWordis identical to standard trie insertsearchneeds DFS to handle wildcards- Early termination: if any branch succeeds, return true immediately
Edge cases:
- Word is all dots: must check all paths of that length
- Multiple dots: backtracking explores all combinations
- Empty word: check if root is marked as end
This pattern combines trie + DFS for pattern matching. It appears in word puzzles and regular expression engines. Time: for addWord, worst case for search with all wildcards. Space: .