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.