# Design Add and Search Words Data Structure

> How to solve Design Add and Search Words Data Structure: extend a trie with depth-first search to support a wildcard dot in queries.

- Difficulty: Medium
- Category: Tries
- Topics: Trie, String, DFS, Design
- Published 2026-08-21

## 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

```typescript
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.

---

Canonical URL: https://www.marauderbot.com/questions/design-add-and-search-words-data-structure
