Blind 75 Visualized

#40 · Tries

Design Add and Search Words Data Structure

Design a WordDictionary with addWord(word) and search(pattern), where a "." in the pattern matches any single letter.

MediumLeetCode
  • Current
  • On path / queued
  • Done
  • Cycle / blocked
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Trie with wildcard search

Words share their prefixes in a trie. A letter in the pattern follows exactly one child; a "." branches into every child at that level, so the search becomes a depth-first walk that tries each branch and backtracks.

Memory layout

Nodes with a child table, or one flat table with 26 slots per node. The search keeps either a recursion stack or an explicit stack of (node, position) pairs.

OperationCost
addWordO(L)
search without "."O(L)
search with dotsO(26^d · L) worst case, d = number of dots; bounded by the number of nodes

Length buckets

Group words by length so a pattern only compares against words that could match. A cheap filter, not a real index.

Memory layout

A hash table from length to a list of words.

OperationCost
addWordO(1) amortized
searchO(k · L), k = words of that length

Why it fits

  • Without dots, search is a straight walk down one path. The trie gives O(L) for that common case.
  • With a dot, all words that share the prefix so far are candidates, and they are exactly the children of one node. The trie already groups candidates for you.
  • Dead branches are cut as soon as a letter has no child, so work is bounded by the part of the trie that really matches the pattern, not by the number of words.

Why alternatives degrade

Hash set of words:
Exact lookups are O(L), but a dot would need all 26 substitutions per dot (26^d lookups) or a scan of every word.
Regex over all words:
Still compares every stored word one by one: O(n·L) per search.
Sorted array + binary search:
Helps for a fixed leading prefix, but a dot in the first positions defeats the ordering.

Four approaches, from naive to production

1 · beginner

Scan every word, compare letter by letter

time addWord O(1), search O(n·L)space O(n·L)

Keep a list of words. For each search, go through every stored word, skip it if the length differs, and compare it to the pattern position by position, treating "." as a match.

class WordDictionary {
    vector<string> words;
public:
    void addWord(string word) {
        words.push_back(word);
    }
    bool search(string pattern) {
        for (const string& w : words) {
            if (w.size() != pattern.size()) continue;
            bool ok = true;
            for (size_t i = 0; i < w.size(); i++) {
                if (pattern[i] != '.' && pattern[i] != w[i]) {
                    ok = false;
                    break;
                }
            }
            if (ok) return true;
        }
        return false;
    }
};

Flaws & bottlenecks

  • Every search touches every stored word, even those that share nothing with the pattern.
  • Work does not shrink when the pattern has few dots or is very specific.
  • Words that share a prefix are compared over and over.

Interviewer cross-questions

Why check the length first?

Say: A "." matches exactly one letter, so a match must have the same length as the pattern. The length test is O(1) and removes most words before any letter is compared.

When is this good enough?

Say: For a tiny dictionary or very few searches. It is also the simplest correct baseline to test a trie against.

What is the worst case?

Say: All n words have the pattern length and agree with it except in the last position: n·L comparisons for one search.

2 · intermediate

Bucket words by length

time addWord O(1), search O(k·L)space O(n·L)

Store words in lists keyed by length. A search looks only at the bucket with the pattern's length and uses a small helper that compares positions and treats "." as a match.

bool matches(const string& w, const string& pattern) {
    for (size_t i = 0; i < w.size(); i++) {
        if (pattern[i] != '.' && pattern[i] != w[i]) return false;
    }
    return true;
}
class WordDictionary {
    unordered_map<int, vector<string>> byLength;
public:
    void addWord(string word) {
        vector<string>& bucket = byLength[word.size()];
        bucket.push_back(word);
        // bucket is a reference, so the map entry is already updated
    }
    bool search(string pattern) {
        static const vector<string> none;
        auto it = byLength.find(pattern.size());
        const vector<string>& bucket = it == byLength.end() ? none : it->second;
        for (const string& w : bucket) {
            if (matches(w, pattern)) return true;
        }
        return false;
    }
};

Flaws & bottlenecks

  • Still a linear scan within the bucket: if most words have the same length, nothing is saved.
  • No sharing of prefixes, so a specific pattern still compares against every word of that length.
  • The helper compares a full word even when the first letter already differs from a non-dot letter (it returns early, but only after reading that letter).

Interviewer cross-questions

How much does bucketing help?

Say: It divides the work by the number of distinct lengths. For natural-language words that is a modest factor; for fixed-length keys such as ids it helps not at all.

How could you filter further?

Say: Index by (length, first letter) when the first pattern character is not a dot. A trie generalizes this idea to every position.

What does a trie improve?

Say: It shares the work of comparing common prefixes and cuts a branch the moment a letter is missing, instead of re-reading every candidate word.

3 · advanced

Trie + recursive search

time addWord O(L), search O(L) without dots, O(nodes) worst case with dotsspace O(total letters) + O(L) recursion

Insert words into a trie. To search, recurse from the root with the pattern position: a letter follows one child, a "." tries every child and returns true if any branch matches. When the pattern is used up, a word must end at that node.

struct TrieNode {
    map<char, TrieNode*> children;
    bool isEnd = false;
};
class WordDictionary {
    TrieNode* root = new TrieNode();
    bool dfs(TrieNode* node, int i, const string& pattern) {
        if (i == (int)pattern.size()) return node->isEnd;
        char ch = pattern[i];
        if (ch == '.') {
            for (auto& kv : node->children) {
                if (dfs(kv.second, i + 1, pattern)) return true;
            }
            return false;
        }
        auto it = node->children.find(ch);
        return it != node->children.end() && dfs(it->second, i + 1, pattern);
    }
public:
    void addWord(string word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (!node->children.count(ch)) node->children[ch] = new TrieNode();
            node = node->children[ch];
        }
        node->isEnd = true;
    }
    bool search(string pattern) {
        return dfs(root, 0, pattern);
    }
};

Flaws & bottlenecks

  • A pattern of all dots visits the whole trie, so the worst case is proportional to the number of nodes.
  • Recursion depth equals the pattern length; very long patterns could overflow a small stack.
  • One hash table per node costs memory and is slower than array indexing for the dense case.

Interviewer cross-questions

Why is a wildcard search a DFS?

Say: A dot creates several candidate branches. Depth-first search explores one fully before trying the next, and returns as soon as one succeeds, so a hit usually costs far less than the worst case.

What is the complexity with many dots?

Say: Bounded by the number of trie nodes, because each node is entered at most once per pattern position. In practice the branching is limited by the words that actually exist.

Why check isEnd at the end of the pattern?

Say: Reaching a node only proves some word has this prefix. The pattern "ba" should not match the stored word "bad" unless "ba" itself was added.

4 · expert

Flat table, explicit stack, length cutoff

time addWord O(L), search O(nodes) worst casespace O(26 · nodes) + stack

Use the flat 26-slot trie and replace recursion with an explicit stack of (node, position) pairs. Remember the longest word added, so any longer pattern is rejected before touching the trie.

class WordDictionary {
    vector<int> next = vector<int>(26, 0);
    vector<bool> end = {false};
    int maxLen = 0;
public:
    void addWord(string word) {
        maxLen = max(maxLen, (int)word.size());
        int node = 0;
        for (char ch : word) {
            int c = ch - 'a';
            if (next[node * 26 + c] == 0) {
                next[node * 26 + c] = end.size();
                end.push_back(false);
                next.insert(next.end(), 26, 0);
            }
            node = next[node * 26 + c];
        }
        end[node] = true;
    }
    bool search(string pattern) {
        if ((int)pattern.size() > maxLen) return false;
        vector<pair<int, int>> stack = {{0, 0}};
        while (!stack.empty()) {
            auto [node, i] = stack.back(); stack.pop_back();
            if (i == (int)pattern.size()) {
                if (end[node]) return true;
                continue;
            }
            if (pattern[i] == '.') {
                for (int c = 0; c < 26; c++) {
                    int child = next[node * 26 + c];
                    if (child != 0) stack.push_back({child, i + 1});
                }
            } else {
                int child = next[node * 26 + (pattern[i] - 'a')];
                if (child != 0) stack.push_back({child, i + 1});
            }
        }
        return false;
    }
};

Flaws & bottlenecks

  • Assumes lowercase letters: other characters would corrupt the slot index.
  • Every node reserves 26 slots, so sparse tries waste memory.
  • The explicit stack can hold up to 26 entries per level for patterns with many dots.

Interviewer cross-questions

Why use an explicit stack?

Say: It removes recursion-depth limits and function call overhead, and the order of exploration becomes visible and controllable. It also makes it easy to bail out the moment one match is found.

What does the length cutoff buy?

Say: A pattern longer than every stored word can never match, so it is rejected in O(1). It is a cheap guard against adversarial long patterns.

How would you speed up patterns that start with dots?

Say: Store a second trie of reversed words and search from whichever end of the pattern has more fixed letters, or keep per-length tries. Both trade memory for speed.

Synchronized code walkthrough

Showing: Scan every word, compare letter by letter — shares the player above; click any step to jump.

class WordDictionary {
    vector<string> words;
public:
    void addWord(string word) {
        words.push_back(word);
    }
    bool search(string pattern) {
        for (const string& w : words) {
            if (w.size() != pattern.size()) continue;
            bool ok = true;
            for (size_t i = 0; i < w.size(); i++) {
                if (pattern[i] != '.' && pattern[i] != w[i]) {
                    ok = false;
                    break;
                }
            }
            if (ok) return true;
        }
        return false;
    }
};