We use analytics and advertising cookies to understand how the site is used and whether our ads on Facebook and Instagram work. They are set only if you accept. See our Privacy Policy for details.
Design a dictionary that supports adding words and searching them with a single-character wildcard.
addWord(word) stores a word.search(pattern) returns true if any stored word matches the pattern. The pattern may contain ., which matches any one character.Implement addAndSearchWords(operations) where operations is a list of [op, ...args]: ["addWord", word] and ["search", pattern]. Return one result per operation - null for addWord, a boolean for search.
A medium trie problem, graded against 6 test cases (3 of them hidden).
A prefix tree for fast string lookup by shared prefix.
Reach for it when you see: Many words, repeated prefix queries, autocomplete, or word-search over a grid.
More Trie problems →A plain hash set handles exact lookups but cannot express a wildcard, because you would have to enumerate every candidate. A trie can, because the wildcard maps naturally onto "branch into all children here".
`addWord` is a standard trie insert with an `isWord` flag on the terminal node. `search` becomes a small DFS over `(node, index)`:
- A concrete character: descend into that one child, or fail if it is absent.
- A `.`: recurse into every child, succeeding if any branch does.
- End of pattern: return `node.isWord`.
That last case is the one people get wrong. Arriving at a valid node only proves the pattern is a prefix of something stored; `"a"` should not match after storing only `"ab"`. The `isWord` check is what separates a match from a prefix.
Cost is driven by the wildcards: with no dots it is O(pattern length), and a leading dot forces a fan-out over the alphabet, so worst case is O(26^d x length) for `d` dots. That is exactly why the constraints cap how many patterns may contain more than two dots - the intended solution is expected to be exponential in the dot count.
The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.
Read off this problem's own test suite, so these are the cases a submission actually has to survive.
These apply to the pattern as a whole, not just this problem.