211. Design Add and Search Words Data Structure

211

MediumTrie and Advanced String SearchPrefix tree + depth-first searchTrie with wildcard DFS backtracking

Design Add and Search Words Data Structure

Design a data structure supporting addWord(word) and search(word). search must return true if any previously added word matches word, where a '.' in the query can match any single letter. Non-dot characters must match exactly.

Open official problem prompt ↗

In plain English

Support insertion of words and matching queries where '.' is a single-character wildcard, answering each query against the whole dictionary.

Picture it like this

Like searching a filing cabinet where some letters of the word you want are smudged: for a clear letter you open exactly one labeled drawer, but for a smudge you must peek into every drawer at that level and see if any leads to a complete match.

Example

Input: addWord("bad"); addWord("dad"); addWord("mad"); search("pad"); search("bad"); search(".ad"); search("b..")
Output: [null, null, null, false, true, true, true]
Why: 'pad' was never added; 'bad' matches exactly; '.ad' matches bad/dad/mad via the wildcard; 'b..' matches 'bad' since the two dots match 'a' and 'd'.

Constraints

1 <= word.length <= 25word in addWord consists of lowercase English lettersword in search consists of '.' or lowercase English lettersThere will be at most 2 dots in a search word (typical constraint)At most 10^4 calls to addWord and search

Pattern lesson

See the pattern, then code

Trie with wildcard DFS backtracking

↗

Trie and Advanced String Search

Repeated prefix lookup, autocomplete, dictionary search, or many-word matching.. Store words in a trie exactly as usual; during search, a concrete letter follows one edge, while a '.' recursively tries every child edge, succeeding if any branch matches the rest of the query.

New words, made simpleKnow these before the algorithm

Wildcard: The '.' character in a query that matches any single letter.
Backtracking DFS: Trying one branch, and if it fails, returning to explore the next branch.
Branching factor: How many children a dot must explore - up to 26 here.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

List of words with pattern match

Every search rescans the entire dictionary; too slow as N grows.

Store words in a list and match each against the query allowing '.'.

Time O(N*L) per searchSpace O(N*L)

Best choiceTrie with DFS on dots

Shares prefixes and only branches where wildcards force it.

Standard trie insert; search descends one child for a letter and all children for a dot.

Time search O(L) typical, O(26^d * L) worstSpace O(total chars)

The rule we keep true

Invariant

At each DFS call, node is the trie node reached by matching query[0:i], and the recursion returns true exactly when some suffix path from node spells the remaining query with is_end at its end.

Why this is correct

Reasoning

For a literal character the match is deterministic, so a single descent is both necessary and sufficient; for '.' the query matches iff at least one child subtree matches the remainder, which is precisely the 'any child succeeds' disjunction the loop computes. Reaching i == len(word) checks is_end so prefixes are not accepted as words.

The algorithm in three movesSay these aloud before coding

1Build a standard trie in addWord with an is_end flag

root children: b, d, m

2For search, run a DFS carrying the current node and query index

'.' branches into b,d,m

3At the end of the query, return the node's is_end flag

each branch matches 'a' then 'd' with is_end -> true

4For a normal character, descend into that specific child if it exists

5For '.', recurse into every child and return true if any recursion succeeds

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Read'bad','dad','mad'

2 · AskWhich root children?

3 · Update stateroot -> b,d,m each spelling _ad

4 · ResultThree chains stored

Key takeaway

The wildcard '.' at position 0 fans out into all root children (b, d, m) before matching 'ad'.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 2-4Node/root shape
Same trie node as problem 208: children map plus end flag.
2
Lines 6-12addWord
Ordinary trie insertion creating a path and marking the final node.
3
Lines 14-16Base case
When the query is exhausted, only an end-of-word node counts as a match.
4
Lines 18-23Wildcard branch
A '.' recurses into every child; success of any branch propagates true.
5
Lines 24-26Literal branch
A concrete letter descends into exactly that child or fails.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

A query of all dots like '...' matches any stored word of that exact length
search for a word shorter or longer than every stored word returns false
A dot at a node with no children returns false
A prefix like 'ba' of stored 'bad' returns false because is_end is not set there

Common beginner mistakes

Returning true at query end without checking is_end (accepts prefixes)
For '.', descending into only one child instead of all
Not short-circuiting the loop when a branch succeeds (still correct but slower)
Treating '.' as a literal character in addWord - dots only appear in search queries

Check your understanding

What is the worst-case cost of a single search, and what input triggers it?

PyPython 3 · solution.py

Optimal

1class WordDictionary:2    def __init__(self):3        self.children = {}4        self.is_end = False56    def addWord(self, word: str) -> None:7        node = self8        for ch in word:9            if ch not in node.children:10                node.children[ch] = WordDictionary()11            node = node.children[ch]12        node.is_end = True1314    def search(self, word: str) -> bool:15        def dfs(node: 'WordDictionary', i: int) -> bool:16            if i == len(word):17                return node.is_end18            ch = word[i]19            if ch == '.':20                for child in node.children.values():21                    if dfs(child, i + 1):22                        return True23                return False24            if ch not in node.children:25                return False26            return dfs(node.children[ch], i + 1)2728        return dfs(self, 0)

Time complexityaddWord O(L); search O(L) with no dots, up to O(26^d * L) worst case with d dotsOptimized

Space complexityO(total characters added); O(L) recursion depth per searchExplained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

FacebookAmazonGoogleUber

Design Add and Search Words Data Structure

Design Add and Search Words Data Structure

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Trie and Advanced String Search