Problem - Add and Search Word

Design a data structure that supports:

• addWord(word): Add word to the structure
• search(word): Return true if word matches. Word may contain '.' which matches any letter.

Example:

addWord("bad")
addWord("dad")
search("pad")  // false
search("bad")  // true
search(".ad")  // true
search("b..")  // true

This extends the basic trie with wildcard matching, requiring backtracking when you encounter '.'.

Constraints: words are lowercase letters only, '.' only appears in search queries, up to $10^4$ operations.