Design Add and Search Words Data Structure — Editorial

Opening the reading…

Intuitionthe pattern determines exactly where branching is necessary

A stored word is a path from the root of a trie. Each letter chooses one edge, and the node reached after the final letter records that a complete word ends there. This lets a search reject a pattern as soon as a required letter is missing, without comparing the pattern with every word that has been added.

A normal letter has only one possible move: follow the child for that letter. A dot has up to 26 possible moves, so the search tries each existing child and continues with the next pattern position. The recursive call represents one possible interpretation of the dots; if any branch reaches a word-ending node exactly when the pattern ends, the search succeeds.

Approachstore prefixes once and branch only for dots

Create an empty trie with a root node, because every word shares the same starting point and the root represents a prefix of length zero.

For each addWord operation, walk through its letters and create a missing child for each letter, because later searches need a distinct edge for every stored prefix.

Mark the node reached after the final letter as a complete word, because reaching a trie node is not enough to prove that a word ends there rather than merely continues.

For each search operation, start a depth-first search at the root and position zero, because the recursive state must identify both the current trie prefix and the pattern character being matched.

If the current pattern character is a letter, follow only its child and return false when that child is absent, because no other edge can match a fixed letter.

If the character is a dot, try every existing child recursively and return true as soon as one branch succeeds, because the dot may represent any lowercase letter and one valid interpretation is sufficient.

When the pattern has been fully consumed, return the current node's isEnd flag, because a prefix such as bad must not match a longer stored word such as badly, and a longer path must not match a shorter word.

Process commands in order, appending null for each insertion and the boolean result for each search, because every operation observes exactly the words inserted before it and contributes one result.

Complexitybranching is limited by the number of wildcard positions

MEASURE	BOUND	WHY
Time	O(n x 26^d) per search and O(n) per insertion	A fixed letter follows one edge, while each dot can multiply the number of active trie paths by at most 26; each visited state advances the pattern position, so the search does not revisit a state within one branch. Since d is at most 2, the alphabet factor is bounded, but the worst case still explores every surviving wildcard branch.
Space	O(T + n) extra, excluding output	The trie contributes one node for each distinct stored prefix character, with T as the worst-case count when inserted words share no prefixes; the recursive search stack holds at most one frame per pattern position, n. The returned result vector is required output and is excluded.

Here n is the length of the current word or search pattern, d is the number of dots in that pattern, and T is the total number of characters in all words currently stored in the trie.

Annotated solutionC++ · trie with recursive wildcard search

CPPA complete trie implementation: insertion creates paths, and search recursively branches only at dots.

#include <string>
#include <vector>

using namespace std;

class WordDictionary {
private:
    struct TrieNode {
        TrieNode* children[26];
        bool isEnd;

        TrieNode() : isEnd(false) {
            for (int i = 0; i < 26; ++i) {
                children[i] = nullptr;
            }
        }
    };

    TrieNode* root;

    bool dfs(TrieNode* node, const string& word, int pos) {
        if (pos == static_cast<int>(word.size())) {
            return node->isEnd;
        }

        char c = word[pos];
        if (c != '.') {
            int index = c - 'a';
            if (node->children[index] == nullptr) {
                return false;
            }
            return dfs(node->children[index], word, pos + 1);
        }

        for (int i = 0; i < 26; ++i) {
            if (node->children[i] != nullptr &&
                dfs(node->children[i], word, pos + 1)) {
                return true;
            }
        }
        return false;
    }

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

    void addWord(const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (node->children[index] == nullptr) {
                node->children[index] = new TrieNode();
            }
            node = node->children[index];
        }
        node->isEnd = true;
    }

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

class Solution {
public:
    vector<string> run(vector<string>& commands,
                       vector<vector<string>>& args) {
        WordDictionary dictionary;
        vector<string> result;

        for (int i = 0; i < static_cast<int>(commands.size()); ++i) {
            if (commands[i] == "addWord") {
                dictionary.addWord(args[i][0]);
                result.push_back("null");
            } else if (commands[i] == "search") {
                result.push_back(dictionary.search(args[i][0]) ? "true" : "false");
            }
        }
        return result;
    }
};

The base case is deliberately node->isEnd rather than true. The trie can represent both a word and a longer word on the same path, so consuming the pattern proves only that the path exists. The ending marker supplies the missing information about whether the path itself was added as a word.

The iterative alternativethe same search with an explicit stack

An iterative search is a reasonable alternative when you want to avoid recursive call-stack usage or make the pending wildcard branches visible. It is not an asymptotic optimisation: the explicit stack stores the same possible states that recursion would store implicitly. The benefit is control over that memory and no dependence on the runtime call-stack limit; the cost is more bookkeeping.

CPPAn explicit-stack version that stores each pending trie node and pattern position.

#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

class WordDictionary {
private:
    struct TrieNode {
        TrieNode* children[26];
        bool isEnd;

        TrieNode() : isEnd(false) {
            for (int i = 0; i < 26; ++i) {
                children[i] = nullptr;
            }
        }
    };

    TrieNode* root;

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

    void addWord(const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (node->children[index] == nullptr) {
                node->children[index] = new TrieNode();
            }
            node = node->children[index];
        }
        node->isEnd = true;
    }

    bool search(const string& word) {
        stack<pair<TrieNode*, int>> pending;
        pending.push({root, 0});

        while (!pending.empty()) {
            TrieNode* node = pending.top().first;
            int pos = pending.top().second;
            pending.pop();

            if (pos == static_cast<int>(word.size())) {
                if (node->isEnd) {
                    return true;
                }
                continue;
            }

            char c = word[pos];
            if (c != '.') {
                int index = c - 'a';
                if (node->children[index] != nullptr) {
                    pending.push({node->children[index], pos + 1});
                }
            } else {
                for (int i = 0; i < 26; ++i) {
                    if (node->children[i] != nullptr) {
                        pending.push({node->children[i], pos + 1});
                    }
                }
            }
        }
        return false;
    }
};

class Solution {
public:
    vector<string> run(vector<string>& commands,
                       vector<vector<string>>& args) {
        WordDictionary dictionary;
        vector<string> result;

        for (int i = 0; i < static_cast<int>(commands.size()); ++i) {
            if (commands[i] == "addWord") {
                dictionary.addWord(args[i][0]);
                result.push_back("null");
            } else if (commands[i] == "search") {
                result.push_back(dictionary.search(args[i][0]) ? "true" : "false");
            }
        }
        return result;
    }
};