Frontend Beauty
ESC

Type to search the knowledge base.

Design Add and Search Words

Word dictionary with '.' wildcards — trie insert, recursive search over branches, and complexity tradeoffs.

intermediate3 min read
  • dsa
  • trie
  • interview
  • Google
  • Meta

The problem

Design a data structure that supports:

  • addWord(word) — add a word
  • search(word) — true if any added word matches; '.' matches any letter
addWord("bad"); addWord("dad"); addWord("mad");
search("pad") → false
search("bad") → true
search(".ad") → true
search("b..") → true

Brute: store list + regex

Keep an array of words; search with a RegExp built from the pattern. Fine for tiny n; O(W · L) per search over all words. Interviewers want a trie.

Trie + DFS on dots

class TrieNode {
  children = new Map<string, TrieNode>();
  end = false;
}

class WordDictionary {
  private root = new TrieNode();

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

  search(word: string): boolean {
    const dfs = (i: number, node: TrieNode): boolean => {
      if (i === word.length) return node.end;
      const ch = word[i];
      if (ch === ".") {
        for (const child of node.children.values()) {
          if (dfs(i + 1, child)) return true;
        }
        return false;
      }
      const next = node.children.get(ch);
      if (!next) return false;
      return dfs(i + 1, next);
    };
    return dfs(0, this.root);
  }
}
op time (typical) space
addWord O(L) O(L) new nodes
search no dots O(L) O(L) stack
search with dots O(26^d · L) worst O(L)

d = number of dots; branching over alphabet.

Object children vs Map

// array of 26 if only lowercase a-z
children: (TrieNode | undefined)[] = Array(26);

Slightly faster constant factors; Map is clearer if charset is open.

Edge cases

  • Empty word (confirm constraints)
  • Search before any add → false
  • All dots "..." — explores entire level
  • Word longer than any path → false early

Common mistakes

  • Treating '.' as literal key in the map
  • Returning true on prefix without end flag
  • Not backtracking (DFS must try all children for dots)

Interview delivery

  1. Trie for prefix sharing.
  2. Insert straightforward.
  3. Search: branch on ..
  4. Complexity with wildcards.
  5. Optional: 26-array nodes.

Mental model

A trie shares prefixes. Wildcards force branching search: . means “try every child.” Without dots, search is a single walk.

If search is hot and inserts rare, you could also keep a list per length and regex — still mention trie as the designed structure.

Complexity honesty

Worst-case search with all dots on a dense trie explores large fractions of the tree. Say O(26^L) style bounds so you don’t claim O(L) for dotted queries.

Out-loud answer

“Trie with end markers. Insert walks/creates nodes. Search DFS: letter follows one edge, dot iterates children. Missing path returns false. Add is O(L); search depends on wildcards.”

Further reading