Design Add and Search Words Data Structure
Support addWord(word) and search(word), where '.' in a search matches any one letter. (In the playground, each line is one operation.)
A way to picture it
A crossword solver's dictionary. When a clue says “b _ _”, you can't take a single path down the letter tree — at every blank, you try each branch in turn, backing out of dead ends until one route spells a real word.
How to approach it
Store words in a trie. Search recursively: a letter follows one child, while '.' tries every child. Succeed only at a word-end mark.
Example
Input: {"ops":["add bad","add dad","add mad","search pad","search bad","search .ad","search b.."]}. Output: [null,null,null,false,true,true,true].
Complexity: O(L) add, up to O(26^L) search time and O(total letters) space. Dots can force the search to branch at every position.
This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.