How do you approach Design Add and Search Words (Wildcard Search)?

Store the words in a trie with an isWord flag on nodes that end a word. addWord is the standard insert.

What is the time complexity of Design Add and Search Words (Wildcard Search)?

Time complexity: O(L) per exact search; O(26^d x L) with d wildcards.. Space complexity: O(total characters stored).

What are common mistakes on Design Add and Search Words (Wildcard Search)?

Leaving out the end-of-word flag, so a lookup reports words that were never inserted. Allocating a fixed 26-child array per node for a sparse alphabet, when a map keeps the memory honest. Not handling the empty string, which is a valid prefix of everything.

gitGood.dev

← Back to problems

Design Add and Search Words (Wildcard Search)

MediumData Structures

Description

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`.

Example 1

Input: operations = [["addWord","bad"],["addWord","dad"],["addWord","mad"],["search","pad"],["search","bad"],["search",".ad"],["search","b.."]]

Output: [null, null, null, false, true, true, true]

Example 2

Input: operations = [["addWord","a"],["search","."],["search","a"],["search","aa"]]

Output: [null, true, true, false]

Example 3

Input: operations = [["search","a"]]

Output: [false]

Constraints

- 1 <= word length <= 25 - word consists of lowercase English letters - pattern consists of lowercase letters and '.' - At most 10^4 operations, of which at most 3 contain more than 2 dots.

Design Add and Search Words (Wildcard Search): approach, complexity and pitfalls

A medium trie problem, graded against 6 test cases (3 of them hidden).

The pattern: Trie

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 Trieproblems →

If you are stuck

Show the 3-step hint ladder

Store the words in a trie with an isWord flag on nodes that end a word. addWord is the standard insert.
search needs backtracking. Write a recursive helper taking (node, index): a normal character follows one child, a '.' tries EVERY child.
The base case is index === pattern.length: return whether the current node is marked as a word end. Reaching a node is not the same as matching a word.

The optimal approach

Show the approach: Trie plus DFS backtracking

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.

Time: O(L) per exact search; O(26^d x L) with d wildcards.
Space: O(total characters stored)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.

Common Trie mistakes

These apply to the pattern as a whole, not just this problem.

Leaving out the end-of-word flag, so a lookup reports words that were never inserted.
Allocating a fixed 26-child array per node for a sparse alphabet, when a map keeps the memory honest.
Not handling the empty string, which is a valid prefix of everything.