Design a structure that stores words and supports searching for a word, where a search pattern may contain the wildcard . that matches any single letter.
The structure supports two operations:
- "addWord" — add the word word to the structure. Returns null.
- "search" — return true if any stored word matches the pattern word, otherwise false. A literal letter must match that exact letter; a . matches any one letter. The pattern matches a stored word only if they are the same length and every position matches.
You are given the operations as two parallel arrays: operations[i] is the operation name and values[i] is its argument list ([word] for both operations). Apply them in order and return an array holding each operation's return value (null for every "addWord", a boolean for each "search").
For example ["addWord","addWord","addWord","search","search","search","search"] with [["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]] returns [null, null, null, false, true, true, true]. After adding "bad", "dad", "mad": search("pad") is false (no stored word); search("bad") is true; search(".ad") is true (matches all three); search("b..") is true (matches "bad").
Example
search(".ad") matches bad/dad/mad; search("b..") matches bad; search("pad") matches nothing stored.
Constraints
- 1 <= operations.length <= 10^4
- operations[i] is one of "addWord", "search".
- 1 <= word.length <= 25
- word in addWord consists of lowercase English letters only.
- word in search consists of lowercase English letters and the character '.'.
- There are at most 3 dots in a search word.
Intuition
Without the wildcard, this is an exact-match dictionary — a set of words would do. The twist is that a search pattern may contain ., which matches any single letter, and the pattern matches only a word of the same length where every other position agrees.
The brute force leans on that: store the words in a set bucketed by length, and for each search compare the pattern against every stored word of that length, character by character, treating . as a free match. (As with the trie, this is an op-replay function — runWordOps returns null for each addWord and a boolean for each search.)
function runWordOps(operations, values) {
const words = []; // every added word
const result = [];
const matches = (pattern, word) => {
if (pattern.length !== word.length) return false;
for (let k = 0; k < word.length; k++) {
// A '.' matches anything; a literal must match exactly.
if (pattern[k] !== "." && pattern[k] !== word[k]) return false;
}
return true;
};
for (let i = 0; i < operations.length; i++) {
const arg = values[i][0];
if (operations[i] === "addWord") {
words.push(arg);
result.push(null);
} else {
// Test the pattern against every stored word.
result.push(words.some((w) => matches(arg, w)));
}
}
return result;
}Every search rescans the whole dictionary — O(W · L) per query — and a pattern like ".at" re-derives from scratch what a shared structure could remember. Can we do better?
The key observation: store the words in a trie so words sharing a prefix share a path. A literal character then follows its one matching child, pruning every other branch at once. The . is the only complication — since it could be any letter, it can't pick one child, so it branches into all of them and succeeds if any branch matches the rest of the pattern. That turns search into a depth-first recursion over the trie that backtracks across a node's children at each wildcard.
A branching trie has no single-lane picture, so the walkthrough traces the wildcard search ".ad" against a trie holding "bad", "dad", "mad" as a decision sequence: the dot at position 0 tries each root child in turn, and within each it must still match a then d and land on an end node (•). The lane is the recursion's path, one branch attempt per frame. (dfs(word, i, node) in the code is this recursion — i is the lane position, node the trie node it currently sits on.) Walking it through:
search ".ad" over { bad, dad, mad } — each frame is one branch the wildcard tries
The pattern starts with a wildcard, so the recursion must try the b-, d-, and m-branches in turn.
First branch tried, b: match 'a' then 'd', land on an end node. "bad" matches — the search can stop and return true.
Had b failed, the d-branch spells "dad" and also reaches an end node — any one match suffices.
A contrasting query: the literal 'a' at position 0 finds no a-edge at the root, so the whole search fails immediately — no branching needed.
An all-wildcard "..." walks any length-3 path; every stored word is length 3 and flagged, so it matches.
But "...." needs a length-4 word; every branch runs off the end before consuming the pattern, so it returns false.
Optimization
Trie with wildcard-aware DFS
Store words in a trie — each node has a children map (character → node) and an isEnd flag. addWord walks/creates the path and marks the final node, exactly like a plain trie.
search is where the wildcard lives. Walk the pattern character by character: a literal letter follows the one matching child if it exists. A `.` could match any letter, so it branches — recurse into every child and succeed if any branch matches the rest of the pattern. The match succeeds only when the pattern is fully consumed and the node we land on has isEnd set (so the pattern matched a complete word, not just a prefix).
addWord is O(L). A literal search is O(L); a search with d wildcards can fan out to O(26^d · L) in the worst case, but the constraint caps the wildcards so it stays cheap. We replay the operations, pushing null for each add and the boolean for each search.
function runWordOps(operations, values) {
// Trie node: children keyed by character, plus a flag marking a complete word.
const makeNode = () => ({ children: new Map(), isEnd: false });
const root = makeNode();
const addWord = (word) => {
let node = root;
for (const ch of word) {
if (!node.children.has(ch)) node.children.set(ch, makeNode());
node = node.children.get(ch);
}
node.isEnd = true; // last node closes the word
};
// Match `word[i..]` against the subtree rooted at `node`.
const dfs = (word, i, node) => {
if (i === word.length) return node.isEnd; // pattern consumed → must be a word end
const ch = word[i];
if (ch === ".") {
// Wildcard: any child could work, so try them all.
for (const child of node.children.values()) {
if (dfs(word, i + 1, child)) return true;
}
return false;
}
// Literal: only the matching child can continue the match.
const child = node.children.get(ch);
return child !== undefined && dfs(word, i + 1, child);
};
const result = [];
for (let i = 0; i < operations.length; i++) {
const arg = values[i][0];
if (operations[i] === "addWord") {
addWord(arg);
result.push(null);
} else {
result.push(dfs(arg, 0, root));
}
}
return result;
}Complexity analysis
Time complexity: O(L) for addWord; search is O(L) with no wildcards and up to O(26^d · L) with d wildcards. Here's why:
addWordwalks/creates one node per character —O(L).- A literal search follows a single path —
O(L). - Each
.forces the recursion to branch into every child (up to 26), sodwildcards can fan out toO(26^d · L).
With the wildcard count capped small (the constraints bound the dots), search stays cheap in practice — O(L) dominated by the path length.
Space complexity: O(N). Here's why:
- The trie holds at most one node per character of the stored words, sharing prefixes — O(N) in their total length.
- The wildcard search adds O(L) recursion-stack depth.
So the structure is O(N); the result array is O(m) over m operations.
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| operations = ["search"]values = a | [false] | Search before any add — empty structure misses. |
| operations = ["addWord","search","search"]values = cat cat dog | [null,true,false] | Exact match hits; a different word misses. |
| operations = ["addWord","search","search"]values = bad .ad ba. | [null,true,true] | Leading and trailing wildcards both match the one stored word. |
| operations = ["addWord","search","search"]values = dog ... .. | [null,true,false] | All-wildcard matches a same-length word but fails on a length mismatch. |
| operations = ["addWord","addWord","addWord","search","search"]values = abc abd xyz ab. .b. | [null,null,null,true,true] | A wildcard must try several children; both patterns find a completing path. |
| operations = ["addWord","search"]values = abcd a.c | [null,false] | A wildcard path that explores children but dead-ends on length before the end. |
Try it yourself
Write your solution against the real judge before checking the reference.