62.Design Add and Search Words Data Structure

MediumBlind 75Tries · 2/3

Problem

Design a data structure that supports adding words and checking whether a string matches any previously added word. Implement WordDictionary:

WordDictionary() initializes the object.
void addWord(String word) adds word.
boolean search(String word) returns true if some added word matches word. word may contain dots '.', and a dot matches any single letter.

A match must have the same length as the stored word.

Examples

Input:  ["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
        [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output: [null,null,null,null,false,true,true,true]
Explanation: ".ad" matches bad/dad/mad; "b.." matches bad.

Input:  ["WordDictionary","addWord","search","search"]
        [[],["a"],["."],["a."]]
Output: [null,null,true,false]
Explanation: "." matches "a"; "a." needs a 2-letter word.

Constraints

1 <= word.length <= 25
word in addWord consists of lowercase English letters.
word in search consists of '.' or lowercase English letters.
There are at most 2 dots in word for search queries.
At most 10^4 calls in total to addWord and search.

💡 Key Insight

Store words in a trie. A normal letter follows exactly one child; a '.' must try every existing child, which turns search into a DFS over the trie. Because tries share prefixes and queries contain at most 2 dots, the branching stays small and only paths that actually exist are explored.

Brute Force (List of Words)

TimeO(1) for addWord; O(n · L) for searchSpaceO(total characters added).

Intuition

Keep every word in a list. For a query, compare it against each stored word character by character, treating '.' as a wildcard. Simple, but each query touches every stored word.

Algorithm

addWord: append to words.
search: for each stored w, skip if lengths differ; otherwise compare each position — a mismatch only counts when the query char is not '.'.
Return true on the first full match, else false.

Visualization

words = [bad, dad, mad]     query = ".ad"

bad: . vs b ok, a=a, d=d  -> match -> true

Code

java

import java.util.ArrayList;
import java.util.List;

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

    public WordDictionary() {
    }

    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 stored, String pattern) {
        if (stored.length() != pattern.length()) {
            return false;
        }
        for (int i = 0; i < pattern.length(); i++) {
            char p = pattern.charAt(i);
            if (p != '.' && p != stored.charAt(i)) {
                return false;
            }
        }
        return true;
    }
}

Complexity

Time: O(1) for addWord; O(n · L) for search — n stored words, L characters each.
Space: O(total characters added).

Bucket by Length

SpaceO(total characters added)

Intuition

A pattern can only match words of the same length. Grouping words into Map<Integer, List<String>> by length skips every word of the wrong length, and exact (dot-free) queries can be answered with a HashSet. Worst case is unchanged when all words share a length, but typical queries scan far fewer words.

Algorithm

addWord: add to exact set and to byLength[word.length()].
search: if no '.' in the query, return exact.contains(word).
Otherwise scan only byLength.get(word.length()) with the wildcard comparison.

Visualization

byLength = { 3: [bad, dad, mad], 5: [apple] }

search("b..")  -> only scan bucket 3 -> "bad" matches
search("pad")  -> no dots -> exact set lookup -> false

Code

java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

class WordDictionary {
    private final Set<String> exact = new HashSet<>();
    private final Map<Integer, List<String>> byLength = new HashMap<>();

    public WordDictionary() {
    }

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

    public boolean search(String word) {
        if (word.indexOf('.') < 0) {
            return exact.contains(word); // no wildcard: O(L) hash lookup
        }
        List<String> bucket = byLength.get(word.length());
        if (bucket == null) {
            return false;
        }
        for (String w : bucket) {
            boolean ok = true;
            for (int i = 0; i < word.length() && ok; i++) {
                char p = word.charAt(i);
                ok = p == '.' || p == w.charAt(i);
            }
            if (ok) {
                return true;
            }
        }
        return false;
    }
}

Complexity

Time: O(L) for addWord and dot-free search; O(k · L) for wildcard search, where k is the number of words with that length.
Space: O(total characters added) — each word stored twice.

Trie + DFSOptimal

TimeO(L) for addWord. search is O(L) without dots; with d dots it is O(26^d · L) in the worst caseSpaceO(N · 26) for the trie with N nodes, plus O(L) recursion depth.

Intuition

Insert words into a 26-ary trie. To search, recurse with (index, node): for a letter, step into that single child; for '.', try every non-null child and succeed if any branch succeeds. At the end of the pattern, the match is valid only if node.isEnd. Dead branches are pruned immediately because missing children are never visited.

Algorithm

addWord: standard trie insert, mark last node isEnd.
dfs(word, i, node):
- If i == word.length(), return node.isEnd.
- If word[i] == '.', for each non-null child, if dfs(word, i + 1, child) return true; return false.
- Else move to children[word[i] - 'a']; return false if null, otherwise recurse.
search(word) = dfs(word, 0, root).

Dry Run

Trie after adding bad, dad, mad; searching ".ad":

flowchart TD
    R["root<br/>query char '.'"] -->|"try b"| B["b"]
    R -->|"try d"| D["d"]
    R -->|"try m"| M["m"]
    B -->|"a"| BA["ba"]
    BA -->|"d"| BAD["bad, isEnd"]
    BAD --> OK["i == 3 and isEnd<br/>return true"]
    D -.->|"never explored"| DA["da"]

The first branch (b) already succeeds, so d and m are never expanded.

Code

java

class WordDictionary {
    private static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isEnd;
    }

    private final TrieNode root = new TrieNode();

    public WordDictionary() {
    }

    public void addWord(String word) {
        TrieNode node = root;
        for (int k = 0; k < word.length(); k++) {
            int c = word.charAt(k) - 'a';
            if (node.children[c] == null) {
                node.children[c] = new TrieNode();
            }
            node = node.children[c];
        }
        node.isEnd = true;
    }

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

    private boolean dfs(String word, int i, TrieNode node) {
        if (i == word.length()) {
            return node.isEnd; // must consume the whole pattern at a word end
        }
        char ch = word.charAt(i);
        if (ch == '.') {
            // wildcard: any existing child may continue the match
            for (TrieNode child : node.children) {
                if (child != null && dfs(word, i + 1, child)) {
                    return true;
                }
            }
            return false;
        }
        TrieNode next = node.children[ch - 'a'];
        return next != null && dfs(word, i + 1, next);
    }
}

Complexity

Time: O(L) for addWord. search is O(L) without dots; with d dots it is O(26^d · L) in the worst case — at most 2 dots here, so bounded by O(676 · L).
Space: O(N · 26) for the trie with N nodes, plus O(L) recursion depth.

Complexity Comparison

Approach	addWord	search	Space
List of Words	O(1)	O(n · L)	O(total chars)
Bucket by Length	O(L)	O(k · L)	O(total chars)
Trie + DFS	O(L)	O(L) to O(26^d · L)	O(nodes · 26)

Common Pitfalls

Returning true when the pattern is consumed without checking isEnd — "ba" must not match after adding only "bad".
For '.', returning the result of the first child's DFS instead of trying all children until one succeeds.
Treating '.' as matching zero or many characters — it matches exactly one letter.
Computing '.' - 'a' as an index (negative) when the wildcard branch is not handled first.