#211 Design Add and Search Words Data Structure

frequently reported atByteDance / TikTok Amazon Apple Microsoft Meta Google

the problem

In plain words

Design WordDictionary with addWord(word) and search(pattern), where the pattern may contain . meaning "any one letter". Return whether some added word matches.

in addWord("bad"), addWord("dad"), addWord("mad"), search("pad"), search("bad"), search(".ad"), search("b..")

out null, null, null, false, true, true, true

1 ≤ word.length ≤ 25
addWord: lowercase letters; search: lowercase letters or '.'
At most 2 dots per search query
At most 10⁴ calls

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

Design: implement every operation. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternTrie (prefix tree)

A normal letter has exactly one child to follow. A dot means "try every child" — so search is a DFS on the trie that only branches at the dots.

solutions

From brute force to optimal

Store every word; on search, compare the pattern with each same-length word, letting '.' match anything.

addWord → list.add(word).
search → for each word of equal length, compare char by char (dot = wildcard).

timeO(1) add, O(N·L) search

Every search may compare against all N words of length L.

spaceO(S)

The stored words.

javalist versionjava.util.*

1class WordDictionaryList {2    private final List<String> words = new ArrayList<>();3 4    public void addWord(String word) {5        words.add(word);6    }7 8    public boolean search(String pattern) {9        for (String w : words) {10            if (matches(w, pattern)) return true;11        }12        return false;13    }14 15    private boolean matches(String word, String pattern) {16        if (word.length() != pattern.length()) return false;17        for (int i = 0; i < word.length(); i++) {18            char p = pattern.charAt(i);19            if (p != '.' && p != word.charAt(i)) return false;20        }21        return true;22    }23}

Insert words into a trie. Search recursively: a letter follows one child, a dot tries all non-null children.

dfs(pattern, i, node): if i == length → return node.isEnd.
If pattern[i] is '.', return true if any child's dfs(i+1) succeeds.
Otherwise follow the single child for that letter (false if missing).

timeO(L) add; search O(L) without dots, O(26ᵏ·L) worst with k dots

Each dot can fan out to at most 26 children; with k ≤ 2 that is at most 676 paths — and never more than the nodes in the trie.

spaceO(S·26) trie + O(L) recursion

Nodes for all letters; the DFS is at most L deep.

javaclass WordDictionary (trie)java.util.*

1class WordDictionary {2    private static class Node {3        Node[] children = new Node[26];4        boolean isEnd;5    }6 7    private final Node root = new Node();8 9    public void addWord(String word) {10        Node cur = root;11        for (char ch : word.toCharArray()) {12            int i = ch - 'a';13            if (cur.children[i] == null) cur.children[i] = new Node();14            cur = cur.children[i];15        }16        cur.isEnd = true;17    }18 19    public boolean search(String pattern) {20        return dfs(pattern, 0, root);21    }22 23    private boolean dfs(String pattern, int i, Node node) {24        if (i == pattern.length()) return node.isEnd;   // used every character25        char ch = pattern.charAt(i);26        if (ch == '.') {                                // wildcard: try every child27            for (Node child : node.children) {28                if (child != null && dfs(pattern, i + 1, child)) return true;29            }30            return false;                               // no child led to a word31        }32        Node next = node.children[ch - 'a'];            // normal letter: one path only33        return next != null && dfs(pattern, i + 1, next);34    }35}

sim

Dry run

loading simulation…

javajava.util.*

1class WordDictionary {2    private static class Node {3        Node[] children = new Node[26];4        boolean isEnd;5    }6 7    private final Node root = new Node();8 9    public void addWord(String word) {10        Node cur = root;11        for (char ch : word.toCharArray()) {12            int i = ch - 'a';13            if (cur.children[i] == null) cur.children[i] = new Node();14            cur = cur.children[i];15        }16        cur.isEnd = true;17    }18 19    public boolean search(String pattern) {20        return dfs(pattern, 0, root);21    }22 23    private boolean dfs(String pattern, int i, Node node) {24        if (i == pattern.length()) return node.isEnd;   // used every character25        char ch = pattern.charAt(i);26        if (ch == '.') {                                // wildcard: try every child27            for (Node child : node.children) {28                if (child != null && dfs(pattern, i + 1, child)) return true;29            }30            return false;                               // no child led to a word31        }32        Node next = node.children[ch - 'a'];            // normal letter: one path only33        return next != null && dfs(pattern, i + 1, next);34    }35}

in the room

How to say it in the interview

talk track

Start from LC 208 — this is the same trie; only search changes.
Say: "letters don't branch, dots do", then write the recursive helper with the index i.
Mention the worst case explicitly (all dots) and that the constraint caps dots at 2.

traps

Returning true when the pattern is used up without checking isEnd.
Returning the result of the first child for '.' instead of continuing when it's false.

what they ask next

Follow-ups

What if '*' (any sequence) were allowed?

At '*' you either skip it (i+1, same node) or consume one letter (i, child) — it becomes a DP/DFS over (i, node) pairs; memoize to stay polynomial.

before you submit

Edge cases to test

A pattern of only dots ("...") → true if any word has exactly that length.
A dot whose first child fails must keep trying the other children.
A pattern that matches only a prefix of a word → false (check isEnd).

practise next