LeetCode #211 Medium

Design Add and Search Words Data Structure

Design a dictionary that stores words and searches patterns where . can stand for any single letter.

triedepth-first-searchdesign

02

Intuition

Keeping every word in a list makes insertion easy, but every search has to scan unrelated words and compare their characters again. A trie removes that repeated prefix work because words with the same beginning share the same path. Ordinary letters still choose one child, while . is the only moment when the search must branch. A depth-first search over those wildcard branches is correct because it explores every stored character that could occupy that exact pattern position, and the terminal flag prevents a prefix from being mistaken for a complete word.

How to spot this pattern

Repeated word insertion plus prefix-shaped lookup is a strong trie signal. When one pattern symbol can match any single character, keep normal trie traversal for fixed letters and use DFS only at wildcard positions.

03

Approach

1

Store common prefixes only once

For addWord, walk from the root through one child per character, creating a node only when that edge does not exist. Mark the final node as terminal. The flag matters because the path for bad also exists inside baddie, but only an explicitly completed word should match.

2

Follow one edge for an ordinary letter

During search, a normal character has exactly one possible continuation. If that child is absent, no stored word can match the pattern, so the branch fails immediately. If it exists, advance both the trie node and the pattern index together.

3

Branch only when the pattern contains a dot

For ., recursively try every child of the current node at the next pattern position. Return as soon as one branch reaches a valid word; if every branch fails, the wildcard cannot be satisfied. When all pattern characters are consumed, return the node's terminal flag rather than accepting the path automatically.

04

Solution

▶1class TrieNode:
▶2    def __init__(self):
▶3        self.children = {}
▶4        self.is_word = False
▶5 
▶6class WordDictionary:
▶7    def __init__(self):
▶8        self.root = TrieNode()
▶9 
▶10    def addWord(self, word: str) -> None:
▶11        node = self.root
▶12        for ch in word:
▶13            if ch not in node.children:
▶14                node.children[ch] = TrieNode()
▶15            node = node.children[ch]
▶16        node.is_word = True
▶17 
▶18    def search(self, word: str) -> bool:
▶19        def dfs(node, index):
▶20            if index == len(word):
▶21                return node.is_word
▶22 
▶23            ch = word[index]
▶24            if ch == '.':
▶25                for child in node.children.values():
▶26                    if dfs(child, index + 1):
▶27                        return True
▶28                return False
▶29 
▶30            if ch not in node.children:
▶31                return False
▶32            return dfs(node.children[ch], index + 1)
▶33 
▶34        return dfs(self.root, 0)

05

Common pitfalls

Treating the wildcard as a literal key

✗ Wrong

node = node.children[ch]

✓ Right

for child in node.children.values():

A dot represents every available character at that depth. Looking up a child named . misses every valid wildcard match.

Accepting any consumed path as a word

✗ Wrong

return True

✓ Right

return node.is_word

Consuming the pattern may stop at a non-terminal prefix. The dictionary should match only words that were actually added.

Restarting after choosing a wildcard child

✗ Wrong

if dfs(self.root, index + 1):

✓ Right

if dfs(child, index + 1):

Once a wildcard chooses a character, the rest of the pattern must continue below that child. Restarting at the root combines pieces from unrelated words.

06

Edge cases

A pattern made entirely of dots, such as ...

The DFS explores trie paths of exactly three characters and accepts only a terminal node, so it matches a stored three-letter word but not a longer word sharing that prefix.

Searching a prefix that was never added, such as app after adding apple

Traversal reaches the node for the prefix, but its terminal flag is false, so the search correctly returns false.

Adding the same word more than once

The insertion follows the existing path and sets the same terminal flag again, leaving search behaviour unchanged.

07

Complexity

Time

O(L) for add; O(26^L) worst-case for search

Space

O(total inserted characters)

A search without wildcards follows one path; each dot may branch across the trie.