Design Add and Search Words Data Structure
Design a data structure to add words and search with '.' wildcards.
Examples
Input: [["WordDictionary","addWord","addWord","search","search","search"],[[],["bad"],["dad"],["pad"],["bad"],[".ad"]]]
Output: [null,null,null,false,true,true]
Input: [["WordDictionary","addWord","search"],[[],["a"],["a"]]]
Output: [null,null,true]
Hints
Consider using a recursive approach to handle the wildcard character ('.') by exploring all possible child nodes at each level of the trie.
Optimize the search by pruning branches early when the current prefix does not match any word in the dictionary, reducing unnecessary recursive calls.
Implement memoization or iterative DFS with a stack to avoid stack overflow for very deep tries and improve performance in cases with multiple wildcards.
Related Problems
Design Add and Search Words Data Structure
Design a data structure to add words and search with '.' wildcards.