LeetCode 211 · Tries

Design Add and Search Words Data Structure, explained with a picture

A trie where a dot means “any letter”.

MediumTries
▶ Watch it step by step

The problem

Design a structure with addWord(word) and search(word), where the search word may contain dots, and a dot matches any one letter.

Input:  add bad, add dad, add mad, search pad, search bad, search .ad, search b..
Output: false, true, true, true

Picture it

Same letter tree as a trie. For a normal letter we follow that one branch. When we meet a dot, we don’t know which letter is meant, so we try every branch at that point; if any of them leads to a complete word, the search succeeds.

How to recognise it

  • You store words and search with a pattern where some positions are fixed letters and some are wildcards.
  • Fixed letters narrow the candidates one position at a time, which is exactly how a walk down a trie works.
  • A wildcard means "try every child here", so the walk becomes a depth-first search (DFS) that branches only at wildcards.
  • LeetCode allows up to 10^4 calls, words of up to 25 letters, and at most 2 dots per search, which keeps the branching small.

Start with brute force

Keep a list of words. For a search, compare the pattern with every stored word of the same length, letting . match anything.

class WordDictionaryBrute:
    def __init__(self):
        self.words = []
    def add_word(self, word):
        self.words.append(word)
    def search(self, word):
        return any(len(w) == len(word) and
                   all(p == "." or p == c for p, c in zip(word, w))
                   for w in self.words)

Adding is O(1), but each search is O(N · L) for N words of length L. With 5,000 adds followed by 5,000 searches that miss, that is up to 5,000 × 5,000 × 25 ≈ 6 × 10^8 character comparisons.

From brute force to the idea

  1. Find the waste. A search for bad compares against dad and mad too, even though the first letter already rules them out.
  2. Store words in a trie. add_word is the same as a trie insert: walk with setdefault, then mark the end with "$".
  3. Search recursively by position. search(word, node, i) asks: can word[i:] be matched starting at node? The first call uses the root and position 0.
  4. A letter follows one branch. If word[i] is a letter, the answer is word[i] in node and a match of the rest from that child. A missing letter fails at once.
  5. A dot tries every branch. If word[i] is ".", try every child except the "$" marker, and succeed if any of them matches the rest. any stops at the first success.
  6. At the end, check the marker. When i == len(word), the pattern matched a path; it is a stored word only if "$" is in the node.

This is the key idea: letters walk straight down the trie, and only a dot branches out to all children.

The key idea

Trie + depth-first search: branch over all children on “.”. Plain letters stay O(length).

Python solution

class WordDictionary:
    def __init__(self):
        self.root = {}
    def add_word(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node["$"] = True
    def search(self, word, node=None, i=0):
        node = self.root if node is None else node
        if i == len(word):
            return "$" in node
        if word[i] == ".":                 # try every branch
            return any(self.search(word, kid, i + 1)
                       for ch, kid in node.items() if ch != "$")
        return word[i] in node and self.search(word, node[word[i]], i + 1)

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceadd O(1); search O(N · L): every stored word is comparedO(total characters)
Trie + DFS (shown code)add O(L); search O(L) with no dots, up to O(26^d · L) with d dots (at most 676 paths for 2 dots)O(total characters) for the trie, plus O(L) recursion depth

With no limit on dots, a pattern of all dots can visit every node of the trie, so the worst case is O(size of the trie).

Edge cases

  • The example: after adding bad, dad, mad: pad is False, bad, .ad and b.. are True.
  • All dots (...): matches any stored 3-letter word, True; .... is False because no word has four letters.
  • Pattern shorter than every word (b): the walk ends on a node without "$", so False.
  • Empty pattern: False unless the empty word was added, which marks the root.
  • Recursion depth: at most one call per letter, so 26 frames for a 25-letter word; far below Python's limit.

Common mistakes

  • Iterating over every key including "$" at a dot. The value True is then passed as a node, and the next step raises TypeError (argument of type 'bool' is not iterable).
  • Returning after the first child at a dot instead of trying all of them, so .ad fails when the first child is a b with no ad below it.
  • Forgetting the end marker check, so b.. matches a stored bade's prefix path.
  • Copying the remaining pattern with slices (word[1:]) at every step, which adds O(L) work per call; passing the index i avoids it.
Your turn: count the matches

Add count(word): how many distinct stored words match the pattern. After adding bad, dad, mad, bed (and bad again), count(".ad") is 3 and count("b.d") is 2. Describe your approach, then write it if you like.

Compare with our answer

Use the same DFS, but return numbers instead of booleans. A dot now has to sum the counts of all children, because every branch may contribute matches; any would stop too early. A word added twice still has one end marker, so it is counted once.

class WordCounter(WordDictionary):
    def count(self, word, node=None, i=0):
        node = self.root if node is None else node
        if i == len(word):
            return 1 if "$" in node else 0
        if word[i] == ".":
            return sum(self.count(word, kid, i + 1)
                       for ch, kid in node.items() if ch != "$")
        if word[i] not in node:
            return 0
        return self.count(word, node[word[i]], i + 1)

count("...") is 4. The cost is the same as the worst case of search, since nothing can stop early.

A strong answer mentions: replacing any with sum, why duplicates count once, and that counting cannot short-circuit.

Check what stuck

1. A crossword helper stores a dictionary and answers patterns like c.t or ..ane, where a dot is any letter. Which approach fits best?

2. Why can a search with no dots run in O(L) regardless of how many words are stored?

3. A learner removes if ch != "$" from the dot branch. After adding b and ba, which search now crashes?

Score 60% or more and the lesson is marked complete.