Design Add and Search Words Data Structure

MediumTriesTrieStringDFSDesign

Problem

Design a data structure that stores words and supports two operations: add a word, and check whether any stored word matches a query string. The query may contain the special character "." which can stand in for any single letter, so one query can match several stored words of the same length.

Example. After adding "bad", "dad", and "mad", a search for "bad" matches exactly, while a search for ".ad" matches all three, since the dot can substitute for "b", "d", or "m".

Key idea

Storage is the easy part: a trie handles it like a plain word dictionary, with each node's children keyed by letter and a flag marking the end of a word. The complication is the wildcard: a dot can be any letter, so at that position the search can no longer follow one child pointer: it must consider all of them.

Handle this with a depth-first search over the trie, tracking the current node and position in the query. At a normal letter, follow the single matching child, or fail if it does not exist. At a dot, branch into every child the current node has and recurse into each one, succeeding if any branch reaches the end of the query at a node marked as a word ending. This is a trie traversal with backtracking layered on top for the wildcard positions.

Solution

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

class WordDictionary {
  private readonly root: TrieNode = new TrieNode();

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

  search(word: string): boolean {
    return this.dfs(word, 0, this.root);
  }

  private dfs(word: string, index: number, node: TrieNode): boolean {
    if (index === word.length) {
      return node.isEnd; // consumed the whole query, must land on a word ending
    }

    const char = word[index];
    if (char === '.') {
      // wildcard: try every child instead of following one fixed path
      for (const child of node.children.values()) {
        if (this.dfs(word, index + 1, child)) {
          return true;
        }
      }
      return false;
    }

    const child = node.children.get(char);
    return child !== undefined && this.dfs(word, index + 1, child);
  }
}

Complexity

  • Time: O(L) for a query with no dots, where L is the query length; up to O(26^d × L) in the worst case, where d is the number of dots, since each dot can branch into every child.
  • Space: O(total characters stored) for the trie, plus O(L) recursion depth per search.

Watch out for

  • A dot at the very end still requires reaching a node where the word-end flag is set, not just any reachable node.
  • Stop as soon as one branch of a dot succeeds; there is no need to keep exploring siblings once a match is found.

Pattern

This combines trie lookup with backtracking search: whenever a lookup must explore multiple possibilities at a position instead of one fixed path, depth-first search over the trie's branches is the natural extension, the same idea used in wildcard matching and constrained dictionary search.

Related questions