What is the brute force approach and complexity for Design Add and Search Words Data Structure?

Keep words in a list per length; compare the pattern letter by letter with each with time complexity O(N · L) and space complexity O(T).

What is the optimal approach and complexity for Design Add and Search Words Data Structure?

Words share a tree of letters; a plain letter follows one child, a dot tries every child with optimal time complexity O(26^d · L) and space complexity O(T).

How do you identify the pattern for Design Add and Search Words Data Structure?

Look for key signals in the prompt: "stores words to search later" indicates Many words and many lookups → build one structure over the words, not a list to scan.; "`.` matches any one letter" indicates A wildcard lets one position take several paths → a DFS that backs up at each dot.; "matches any previously added string" indicates The whole word must match, so a walk that stops early on a prefix is not a match → keep an end flag on each node..

Design Add and Search Words Data Structure

Medium·LeetCode #211Basic Anchor

LeetCode

Jump:

30-Second Mental ModelTrie + DFS search (back up at each wildcard)

Complexity:O(N · L)→O(26^d · L)

Key Insight

Store every word in a trie: one node per letter, with words that share a start sharing the top of the path. Each node has up to 26 children, and isEnd is set only on the node where a word ends. search walks the pattern down the trie. A letter follows one child. A . tries every child in turn and backs up after each failure. It returns true only if it uses up the pattern on a node with isEnd set.

Core Validity Invariant

A search returns true only if it uses up the whole pattern and stops on a node with isEnd set. Each letter of the pattern follows a child that really exists, and each . is replaced by a real child.

Problem

Build a class WordDictionary that stores words and answers pattern queries.

WordDictionary() creates an empty dictionary.
addWord(word) stores a word. You can add words at any time.
search(pattern) returns true if some stored word matches the pattern, and false otherwise.

A pattern matches a word only when both have the same length and every letter agrees. The one exception is ., which stands for any single letter. So b.. matches bad, and ..d matches bad, dad and mad. A prefix of a stored word does not count: ba does not match, even though it is the start of bad.

Input

A sequence of calls: addWord(word) with lowercase letters, and search(pattern) with lowercase letters and ..

Output

For each search call, true or false. addWord returns nothing.

Example 1

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

Output: false, true, true, true

pad does not start any stored word. bad is stored. .ad matches bad, dad or mad. b.. matches bad.

Example 2

Input: addWord("bad"), search("ba"), search("...")

Output: false, true

ba is only the start of bad, and no word ends there, so it does not match. ... has three letters, so it matches bad.

Constraints

• 1 ≤ word length ≤ 25
• Words given to `addWord` use only lowercase letters `a` to `z`.
• Patterns given to `search` use lowercase letters and `.`.
• A pattern has at most 2 dots.
• At most 10^4 calls in total to `addWord` and `search`.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
If the pattern has no dots, how would I check whether one stored word matches it, letter by letter?
2.
A . can be any letter. If the pattern is .ad, how many different words could it be, and where do they split?
3.
If I store bad and the pattern is ba, is ba a match? What decides whether a walk through the letters counts as a word?
4.
bad and bat both start with ba. If I store them separately, do I compare b and a twice?
5.
How many stored words would a plain list force me to check for one search if there are 10,000 of them?

Brute force approach

Idea

Two words can only match if they have the same length, so keep one list of words per length. search looks only at the list for its length. It compares the pattern with each word letter by letter. A . in the pattern matches any letter. The first full match returns true.

Thinking process

1
A stored word can only match a pattern of the same length, so grouping the words by length cuts the list we must scan.
2
For each word in that list, compare position by position. At each position the letters must be equal, or the pattern must have a . there.
3
Example: the stored words are bad, dad, mad, cat. search(".ad") only looks at the 3-letter list. . fits b, a equals a, d equals d. So bad matches at once and the search returns true.
4
If one position fails, move on to the next word. If the list runs out, return false.

Code & Implementation

brute.cpp

class WordDictionary {
    // byLength[n] = every stored word with n letters. A match must have the same length.
    vector<vector<string>> byLength;

    // Does a stored word match the pattern? A '.' matches any one letter.
    static bool matches(const string& stored, const string& pattern) {
        for (size_t i = 0; i < stored.size(); i++)
            if (pattern[i] != '.' && pattern[i] != stored[i]) return false;
        return true;
    }

public:
    WordDictionary() {}

    void addWord(string word) {
        if (word.size() >= byLength.size()) byLength.resize(word.size() + 1);
        byLength[word.size()].push_back(word);
    }

    bool search(string word) {
        if (word.size() >= byLength.size()) return false;   // no stored word has this length
        // Compare the pattern with every stored word of the same length.
        for (const string& stored : byLength[word.size()])
            if (matches(stored, word)) return true;
        return false;
    }
};

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

class WordDictionary {
    private List<List<String>> byLength;

    public WordDictionary() {
        byLength = new ArrayList<>();
    }

    public void addWord(String word) {
        while (byLength.size() <= word.length()) {
            byLength.add(new ArrayList<>());
        }
        byLength.get(word.length()).add(word);
    }

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

    public boolean search(String word) {
        if (word.length() >= byLength.size()) return false;
        for (String stored : byLength.get(word.length())) {
            if (matches(stored, word)) return true;
        }
        return false;
    }
}

class WordDictionary:
    def __init__(self):
        self.by_length: list[list[str]] = []

    def addWord(self, word: str) -> None:
        while len(self.by_length) <= len(word):
            self.by_length.append([])
        self.by_length[len(word)].append(word)

    @staticmethod
    def _matches(stored: str, pattern: str) -> bool:
        for s_ch, p_ch in zip(stored, pattern):
            if p_ch != '.' and p_ch != s_ch:
                return False
        return True

    def search(self, word: str) -> bool:
        if len(word) >= len(self.by_length):
            return False
        for stored in self.by_length[len(word)]:
            if self._matches(stored, word):
                return True
        return False

export class WordDictionary {
    private byLength: string[][];

    constructor() {
        this.byLength = [];
    }

    addWord(word: string): void {
        while (this.byLength.length <= word.length) {
            this.byLength.push([]);
        }
        this.byLength[word.length].push(word);
    }

    private matches(stored: string, pattern: string): boolean {
        for (let i = 0; i < stored.length; i++) {
            if (pattern[i] !== '.' && pattern[i] !== stored[i]) return false;
        }
        return true;
    }

    search(word: string): boolean {
        if (word.length >= this.byLength.length) return false;
        for (const stored of this.byLength[word.length]) {
            if (this.matches(stored, word)) return true;
        }
        return false;
    }
}

Complexity

Time O(N · L)Space O(T)

A search that finds no match compares the pattern with every stored word of its length, and each comparison can run up to 25 letters. With thousands of stored words, that is a lot of work per search. The trie pays only for the letters in the pattern (plus the branches the dots open), and it shares work between words that start the same way. addWord is O(L). A search compares with up to N stored words of the same length, L letters each. T is the total number of letters stored.

Optimized approach

Idea

Start from brute force

The brute force keeps the words as separate strings. Every search starts again at the first letter of each word of the right length.

Find the repeated work

Words that share a start (bad, bat, ban) repeat the same first comparisons. And a pattern that already fails on its first letter still gets checked against every word of that length, one at a time.

Define the state — what variables do I need?

root: The empty starting node. Its children are the first letters of the stored words.
node.next[c]: The child for letter `c`, or null when no stored word continues with `c` at this point.
isEnd: True when a stored word ends exactly on this node. The `a` in `ba` is not an end when only `bad` is stored.
i: Position in the pattern that the current DFS call is looking at.

Define validity

Define the transitions — when does each pointer move, and why is it safe?

addWord: for each letter

If `node.next[c]` is null, create it. Move down into `node.next[c]`.

Words that share a start reuse the same nodes, so each prefix is stored once.

addWord: after the last letter

Set `isEnd = true` on that node only.

Only the last node is the end of this word. Setting the flag on the way down would make prefixes look like words.

search: the pattern letter is a normal letter

If `node.next[c]` is null, return `false`. Otherwise move to it.

The letter must match at this position, so only one child can continue the match.

search: the pattern letter is `.`

Try each child in turn. Return `true` as soon as one branch matches the rest of the pattern. If none does, return `false`.

A dot can be any letter, so every child is a candidate. A failed branch is abandoned and the walk backs up to the dot to try the next one.

search: the pattern is used up

Return `node.isEnd`.

The walk has matched every letter. It is a real match only if a word ends on this node.

What does the current window add to the answer?

Each search call returns true or false. addWord only creates the nodes that are missing. A true result means one branch reached the end of the pattern on a word end.

Code & Implementation

optimal.cpp

class WordDictionary {
    struct TrieNode {
        TrieNode* next[26] = {};   // one child slot per letter
        bool isEnd = false;        // a stored word ends exactly on this node
    };
    TrieNode* root;

    // Frees the trie below `node`.
    static void freeTrie(TrieNode* node) {
        if (!node) return;
        for (TrieNode* child : node->next) freeTrie(child);
        delete node;
    }

    // Can the pattern from position i on match a stored word from `node` down?
    bool dfs(TrieNode* node, const string& pattern, int i) {
        if (!node) return false;
        if (i == (int)pattern.size()) return node->isEnd;   // used up: must stop on a word end
        char c = pattern[i];
        if (c != '.') return dfs(node->next[c - 'a'], pattern, i + 1);   // a letter has one child
        // A dot: try every child. If one fails, the loop moves on to the next child.
        for (TrieNode* child : node->next)
            if (child && dfs(child, pattern, i + 1)) return true;
        return false;
    }

public:
    WordDictionary() : root(new TrieNode()) {}

    ~WordDictionary() { freeTrie(root); }

    void addWord(string word) {
        TrieNode* node = root;
        for (char c : word) {
            TrieNode*& child = node->next[c - 'a'];
            if (!child) child = new TrieNode();
            node = child;
        }
        node->isEnd = true;        // mark only the last node, not the prefixes on the way
    }

    bool search(string word) {
        return dfs(root, word, 0);
    }
};

class WordDictionary {
    static class TrieNode {
        TrieNode[] next = new TrieNode[26];
        boolean isEnd = false;
    }

    private final TrieNode root;

    public WordDictionary() {
        root = new TrieNode();
    }

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

    private boolean dfs(TrieNode node, String word, int i) {
        if (node == null) return false;
        if (i == word.length()) return node.isEnd;

        char c = word.charAt(i);
        if (c != '.') {
            return dfs(node.next[c - 'a'], word, i + 1);
        }
        for (int j = 0; j < 26; j++) {
            if (node.next[j] != null && dfs(node.next[j], word, i + 1)) {
                return true;
            }
        }
        return false;
    }

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

class TrieNode:
    def __init__(self):
        self.next: dict[str, TrieNode] = {}
        self.is_end: bool = False

class WordDictionary:
    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.next:
                node.next[ch] = TrieNode()
            node = node.next[ch]
        node.is_end = True

    def _dfs(self, node: TrieNode | None, word: str, i: int) -> bool:
        if not node:
            return False
        if i == len(word):
            return node.is_end

        ch = word[i]
        if ch != '.':
            return self._dfs(node.next.get(ch), word, i + 1)

        for child in node.next.values():
            if self._dfs(child, word, i + 1):
                return True
        return False

    def search(self, word: str) -> bool:
        return self._dfs(self.root, word, 0)

class TrieNode {
    next: (TrieNode | null)[] = new Array(26).fill(null);
    isEnd: boolean = false;
}

export class WordDictionary {
    private root: TrieNode;

    constructor() {
        this.root = new TrieNode();
    }

    addWord(word: string): void {
        let node = this.root;
        for (let i = 0; i < word.length; i++) {
            const idx = word.charCodeAt(i) - 97;
            if (!node.next[idx]) node.next[idx] = new TrieNode();
            node = node.next[idx]!;
        }
        node.isEnd = true;
    }

    private dfs(node: TrieNode | null, word: string, i: number): boolean {
        if (!node) return false;
        if (i === word.length) return node.isEnd;

        const c = word[i];
        if (c !== '.') {
            const idx = word.charCodeAt(i) - 97;
            return this.dfs(node.next[idx], word, i + 1);
        }
        for (let j = 0; j < 26; j++) {
            if (node.next[j] && this.dfs(node.next[j], word, i + 1)) {
                return true;
            }
        }
        return false;
    }

    search(word: string): boolean {
        return this.dfs(this.root, word, 0);
    }
}

Complexity

Time O(26^d · L)Space O(T)

A search with no dots never looks at any other word. The brute force pays for every stored word; the trie pays only for the letters in the pattern, plus the branches the dots open. This problem allows at most 2 dots, so the branching stays small. addWord and a search without dots are O(L). Each dot can branch into up to 26 children, so a search with d dots costs at most O(26^d · L). T is the total number of letters stored; the trie has at most one node per letter.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Keep words in a list per length; compare the pattern letter by letter with each	O(N · L)	O(T)
Optimal	Words share a tree of letters; a plain letter follows one child, a dot tries every child	O(26^d · L)	O(T)

Why does this belong to this pattern?

Clues in the problem statement

“stores words to search later”Many words and many lookups → build one structure over the words, not a list to scan.
“`.` matches any one letter”A wildcard lets one position take several paths → a DFS that backs up at each dot.
“matches any previously added string”The whole word must match, so a walk that stops early on a prefix is not a match → keep an end flag on each node.

one node per letter+a letter follows one child+a dot tries every child (DFS)+true only on an end node→Trie + DFS search (back up at each wildcard)

A trie alone is not enough. Implement Trie's search follows a single path, because every letter is fixed. Here a . makes the walk branch, so the search must try each child and back up after a failure, the same way a grid DFS does. The end check matters just as much: the search must stop on a word end, not just on any node it reaches. Word Search II uses this trie-plus-DFS walk too, but over letters on a board.

Don't make this mistake

Returning true when the walk only reaches a prefix (pattern confusion)

✗ if (i == (int)pattern.size()) return true; // a prefix is not a stored word

✓ if (i == (int)pattern.size()) return node->isEnd;

This is the startsWith check from Implement Trie, not search. Dry run: bad is stored. search("ba") walks root → b → a and uses up the pattern, so the wrong line returns true. But ba was never added. Only the node where the walk stops, checked with isEnd, says whether a word ends there.

Setting isEnd on every node while adding

✗ for (char c : word) { ... node->isEnd = true; // marks every prefix too }

✓ // after the loop, once: node->isEnd = true;

With bad added this way, the nodes for b and ba also become word ends. Then search("b") returns true, even though only bad was added.

A dot that matches no letter

✗ if (c == '.') return dfs(node, pattern, i + 1); // the dot does not move down

✓ for (TrieNode* child : node->next) if (child && dfs(child, pattern, i + 1)) return true; return false;

A dot must use up exactly one letter by moving to a child. In the dry run, .at with bad and cat stored: if the dot does not move down, the walk looks for a at the root, finds no child, and returns false. But cat matches .at.

Trying only the first child of a dot

✗ for (TrieNode* child : node->next) if (child) return dfs(child, pattern, i + 1);

✓ for (TrieNode* child : node->next) if (child && dfs(child, pattern, i + 1)) return true;

In the dry run, the first child of the root is b. For .at, b → a has no t, so the wrong version returns false and never tries c, where cat is. A dot must try every child and back up after each failure.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Trie translate into production architectures and low-level memory mechanics.

LLD Practice

Autocomplete & Search Engine

Prefix query caching, ranking, and memory-efficient trie compaction.

Explore Track

C++ Internals

Memory Alignment & Struct Padding

Minimizing pointer overhead and cache misses across 26-ary trie nodes.

Explore Track

Word Search II