Add and Search Solution

Implement the data structure with wildcard support. Core ideas:

• addWord is identical to standard trie insert
• search needs 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: $O(L)$ for addWord, $O(26^L)$ worst case for search with all wildcards. Space: $O(L)$.