Design Add and Search Words Data Structure

MediumTrie · DFS · Design🧩 Trie LeetCode #211 ↗Updated Oct 30, 2026

Problem

Design WordDictionary with addWord(word), which stores a lowercase word, and search(pattern), which returns true if some stored word matches the pattern. A pattern has the same length as the word it matches; each '.' matches any one letter, every other letter must match exactly.

Inputadd bad, dad, mad; search("pad")Outputfalse

Inputsearch("bad") search(".ad")Outputtrue, true

Inputsearch("b..") search("b.")Outputtrue, false

1 ≤ word.length ≤ 25 · added words are lowercase · at most 2 dots per search · ≤ 10⁴ calls

Try it yourself

Java

class WordDictionary {
    public void addWord(String word) {
        
    }

    public boolean search(String word) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Store words in a trie: a letter follows exactly one edge, and only a '.' branches into all existing children. Prefixes that no word has are pruned immediately instead of being compared word by word.

PatternTrie

Instinct Many words, shared prefixes, and questions like "starts with", autocomplete, wildcard match or "search a board for all these words" - build a prefix tree.

Memory hack Words share their beginnings, so store each beginning once - walk one letter per step, and an end flag marks where a real word stops.

Open the Trie guide →

Approaches

Brute ForceList + Compare Every Word

Time O(1) add, O(N·L) searchSpace O(S)

Keep all words in a list and compare the pattern with each one, letter by letter, treating '.' as a wildcard. N = words, L = length, S = total characters.

Java

class WordDictionary {
    private final List<String> words = new ArrayList<>();

    public void addWord(String word) { words.add(word); }

    public boolean search(String word) {
        for (String w : words) if (matches(w, word)) return true;
        return false;
    }

    private boolean matches(String w, String p) {
        if (w.length() != p.length()) return false;
        for (int i = 0; i < w.length(); i++)
            if (p.charAt(i) != '.' && p.charAt(i) != w.charAt(i)) return false;
        return true;
    }
}

Trivial to write, but every search touches the whole dictionary.

BetterHash Sets Bucketed by Length

Time O(L) add, O(N·L) searchSpace O(S)

One HashSet per length: a dot-free pattern is a single O(L) hash lookup; with dots, only same-length words are scanned.

Java

class WordDictionary {
    private final Map<Integer, Set<String>> byLen = new HashMap<>();

    public void addWord(String word) {
        byLen.computeIfAbsent(word.length(), k -> new HashSet<>()).add(word);
    }

    public boolean search(String word) {
        Set<String> bucket = byLen.getOrDefault(word.length(), Set.of());
        if (word.indexOf('.') < 0) return bucket.contains(word);   // exact lookup
        for (String w : bucket) if (matches(w, word)) return true;
        return false;
    }

    private boolean matches(String w, String p) {
        for (int i = 0; i < w.length(); i++)
            if (p.charAt(i) != '.' && p.charAt(i) != w.charAt(i)) return false;
        return true;
    }
}

Big win for exact queries; wildcard queries remain a scan.

OptimalTrie + DFS on Wildcards

Time O(L) add, O(26^d·L) searchSpace O(26·S)

Insert words into a 26-ary trie. Search recurses: a letter follows one child, a '.' tries every child. With d ≤ 2 dots at most 26^d paths of length L are explored — independent of N.

Java

class WordDictionary {
    private static class Node { Node[] next = new Node[26]; boolean isEnd; }

    private final Node root = new Node();

    public void addWord(String word) {
        Node cur = root;
        for (char c : word.toCharArray()) {
            if (cur.next[c - 'a'] == null) cur.next[c - 'a'] = new Node();
            cur = cur.next[c - 'a'];
        }
        cur.isEnd = true;
    }

    public boolean search(String word) { return dfs(word, 0, root); }

    private boolean dfs(String word, int i, Node node) {
        if (i == word.length()) return node.isEnd;
        char c = word.charAt(i);
        if (c != '.') {
            Node child = node.next[c - 'a'];
            return child != null && dfs(word, i + 1, child);
        }
        for (Node child : node.next) {   // wildcard: try every branch
            if (child != null && dfs(word, i + 1, child)) return true;
        }
        return false;
    }
}

Search cost no longer depends on the number of stored words.

At a glance

Level	Approach	Time	Space
Brute Force	List + Compare Every Word	`O(1) add, O(N·L) search`	`O(S)`
Better	Hash Sets Bucketed by Length	`O(L) add, O(N·L) search`	`O(S)`
Optimal	Trie + DFS on Wildcards	`O(L) add, O(26^d·L) search`	`O(26·S)`

Common pitfalls

Skipping the isEnd check — "b." would wrongly match via "bad".
Regex-matching every word — still O(N·L), plus regex overhead.
Indexing '.' - 'a' — negative index; handle the wildcard first.

Interview tips

Start from the list scan, then ask how to stop comparing words that share no prefix.
Reuse the Trie from LC 208 — only search changes.
State the bounded branching: at most 2 dots ⇒ at most 26² paths.

Pattern

Trie + backtracking → dictionary lookups with wildcards or many patterns sharing prefixes.

My notes saved in this browser