Faangprep Logo
Log inStart free
Browse curriculum

Design Add and Search Words Data Structure

Store words in a trie and search them with '.' wildcards using a DFS that branches at every dot.

MediumSolve on LeetCode

Problem Understanding

Design a WordDictionary with two operations:

  • addWord(word) stores a word.
  • search(word) returns true if any stored word matches, where '.' in the pattern matches any one letter.

Example: after adding bad, dad and mad, search("pad") is false, search("bad") is true, search(".ad") is true and search("b..") is true.

The Intuition: A Trie, and a DFS for the Dots

addWord is the ordinary trie insert. The new part is search.

For a normal letter there is exactly one child to follow. For '.' there may be several, and you do not know which one leads to a match, so try them all: a DFS over (node, index).

  1. If index reaches the end of the pattern, return whether this node ends a word.
  2. If the character is a letter, follow that child, or fail if it is missing.
  3. If it is '.', try every child with index + 1 and return true as soon as one succeeds.

Interactive Walkthrough

Words are added first, then each search walks the trie. The branch being followed is outlined; at a '.', watch the search try one child, back up out of it if it fails, and move on to the next.

Dry Run Table

Stored: bat, bed. Search: b.d

Index Pattern Node Action
0 b root follow b
1 . b try child a
2 d a no d child: back up
1 . b try child e
2 d e follow d
3 end d ends a word: true

The Solution Template

A trie with a DFS search that branches at every '.'.

Design Add and Search Words Data Structure Code
1class WordDictionary {
2    constructor() {
3        this.root = {};
4    }
5

6    addWord(word) {
7        let node = this.root;
8        for (const ch of word) {
9            node = node[ch] ??= {};
10        }
11        node.$ = true;
12    }
13

14    search(word) {
15        const dfs = (node, i) => {
16            if (i === word.length) return node.$ === true;
17            const ch = word[i];
18            if (ch === '.') {
19                return Object.keys(node).some((key) => key !== '$' && dfs(node[key], i + 1));
20            }
21            return node[ch] !== undefined && dfs(node[ch], i + 1);
22        };
23        return dfs(this.root, 0);
24    }
25}

Edge Cases & Common Mistakes

  • A prefix is not a word: with only at stored, search("a") is false. Check the word-end flag at the end of the pattern, not just that the path exists.
  • Returning after the first child at a '.': the first branch may fail while a later one matches; keep trying until one succeeds.
  • A pattern longer than every word: the walk runs out of children and fails; no special case is needed.
  • All dots: search("...") is true if any stored word has exactly three letters.

Summary

Add and Search Words is a trie plus one idea: a '.' is a branch point, so search becomes a DFS that tries each child there and backs up from dead ends. Letters follow a single child, and the end of the pattern checks the word-end flag.

More practice: DSA interview questions with answers · patterns cheat sheet

Previous

Implement Trie (Prefix Tree)

Next

Word Search II

The approach, step by step

  1. Insert with addWord

    Walk the word letter by letter from the root, creating missing children, and mark the last node as a word end.

  2. Search letters directly

    For a letter, follow that child; if it is missing, this branch fails.

  3. Branch on dots

    For '.', try every child with the rest of the pattern and return true on the first success. At the end of the pattern, return the node's word-end flag.

Frequently asked questions

How does a trie handle the '.' wildcard?

A letter has only one child to follow, but '.' could be any letter, so the search tries each child of the current node in turn with a DFS. It returns true on the first branch that matches the rest of the pattern and backs up out of branches that fail.

What is the time complexity of search with wildcards?

Without dots, search is O(L) for a pattern of length L. With dots, the DFS may visit every node of the trie in the worst case, so it is bounded by O(N), where N is the number of nodes, which is at most the total number of letters added.

Why not store words in a hash set?

A set answers exact lookups in O(L), but a pattern with dots would have to be checked against every stored word. The trie shares prefixes, so a wildcard only fans out at the positions where the stored words actually differ.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description