4.15.2 — Design Add and Search Words Data Structure

LeetCode 211 · Medium · ★ Blind 75

The problem

Support addWord(word) and search(word), where the search string may contain . as a wildcard matching any single character.

addWord("bad"); addWord("dad"); addWord("mad")
search("pad")  →  false
search("bad")  →  true
search(".ad")  →  true
search("b..")  →  true

The pattern

The trie from 4.15.1 is unchanged. Only search changes.

Without wildcards, search is a straight walk: at each character there is exactly one child to follow, or the word is absent.

A . breaks that. Any child could be the right one, and you cannot tell which without looking. So the search branches: try every child, and succeed if any branch succeeds.

A search that branches and may need to back out is a depth-first search with backtracking. So the iterative walk becomes recursive.

The solution

Python

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False


class WordDictionary:
    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word: str) -> None:
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_word = True

    def search(self, word: str) -> bool:
        def dfs(index: int, node) -> bool:
            for i in range(index, len(word)):
                c = word[i]

                if c == '.':                                  # try every child
                    for child in node.children.values():
                        if dfs(i + 1, child):
                            return True
                    return False                              # no child worked

                if c not in node.children:
                    return False
                node = node.children[c]

            return node.is_word

        return dfs(0, self.root)

TypeScript

class WordDictionary {
  private root = new TrieNode();

  addWord(word: string): void {
    let node = this.root;
    for (const c of word) {
      if (!node.children.has(c)) node.children.set(c, new TrieNode());
      node = node.children.get(c)!;
    }
    node.isWord = true;
  }

  search(word: string): boolean {
    const dfs = (index: number, start: TrieNode): boolean => {
      let node = start;
      for (let i = index; i < word.length; i++) {
        const c = word[i];

        if (c === '.') {
          for (const child of node.children.values()) {
            if (dfs(i + 1, child)) return true;
          }
          return false;
        }

        const next = node.children.get(c);
        if (!next) return false;
        node = next;
      }
      return node.isWord;
    };

    return dfs(0, this.root);
  }
}

The loop handles ordinary characters iteratively and only recurses on a wildcard. That keeps the recursion depth proportional to the number of dots rather than to the word length, which matters for long words with few wildcards.

The return False after the wildcard loop is essential. If no child leads to a match, this branch has failed and must say so. Falling through would continue the outer loop from the wrong node.

return node.is_word at the end, not return True. Reaching the end of the search string only means a path exists; whether it spells a stored word is what the flag says. This is the same distinction as search versus startsWith in 4.15.1.

Trace

Words bad, dad, mad. Search ".ad".

At the root, the first character is ., so try each child in turn: b, d, m.

Following b: the remaining pattern is "ad", which walks a then d and lands on a node with is_word set. Return true, and the other branches are never tried.

Search "b.." walks b deterministically, then branches on the first dot — but b has only the child a, so there is only one branch, and then only one more. It matches.

Complexity

Without wildcards: O(L) for a word of length L, exactly as before.

With wildcards: each . multiplies the work by the number of children at that node, up to 26. So the worst case is O(26^d \cdot L) where d is the number of dots.

In practice it is far cheaper, because most branches die immediately — a real trie is sparse, and a node rarely has all 26 children.

A leading . is the expensive case, because the root usually does have many children. A dot deep in the word costs almost nothing.

Space is O(\text{total characters added}).

Where this goes next

• Word Search II — a trie plus backtracking over a grid instead of a string. That is 4.15.3, and it is the same combination taken further.
• Regular Expression Matching — . plus *, which needs dynamic programming because a star can match any number of characters and greedy branching no longer terminates cleanly. 4.24.
• Wildcard Matching — ? and * against a single string, also DP.

The rule: a deterministic walk becomes a depth-first search the moment a step has more than one legal continuation.

What the interviewer will push on

"What is the worst-case complexity?" O(26^d \cdot L) for d wildcards, and say that a leading dot is the expensive position.

"Why recursion here but not in the plain trie?" Because a wildcard makes the walk branch, and a branch that can fail needs to back out.

"Why return node.is_word and not return True?" A path existing is not the same as a word ending there.

"How would you handle * as well?" That is a different problem — a star matches any number of characters, so the search space stops being a simple tree walk and you move to DP.

"Could you speed up many wildcard searches?" If searches are frequent and the word set is fixed, index words by length and by known character positions, so a pattern only ever searches the words that could possibly match.

One thing to volunteer: say that only search changes, and that the change is exactly "one child becomes all children". Naming the minimal difference from the previous problem is a strong signal.

Next: 4.15.3 Word Search II — the hardest problem in this group, where a trie turns an impossible search into a fast one.