Design Add and Search Words Data Structure — Trie + Wildcard DFS

Problem Statement#

LeetCode 211 — Design Add and Search Words Data Structure | Difficulty: Medium

Design a data structure WordDictionary that supports:

• addWord(word) — Adds a word into the dictionary.
• search(word) — Returns true if any string in the dictionary matches word. The search string may contain the wildcard character . which matches any single letter.

Constraints:

• 1 <= word.length <= 25
• word in addWord consists of lowercase English letters only.
• word in search consists of lowercase letters or ..
• At most 2 dots per search call (per LeetCode constraints — but practical solutions handle any number).
• At most 10^4 calls to addWord and search.

Examples:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad")  → false
search("bad")  → true
search(".ad")  → true   (matches "bad", "dad", or "mad")
search("b..")  → true   (matches "bad")

Why This Problem Matters#

This is one of the cleanest demonstrations of why a trie is dramatically more powerful than a hash set. With a hash set, supporting wildcard search like .ad would cost O(N times L) per query — you would have to scan every stored word. With a trie, the wildcard query becomes a controlled DFS that prunes whole subtrees as soon as a character fails to match.

It is asked at Google, Amazon, Facebook, and Microsoft because it tests three skills at once — designing a class around a data structure, implementing the trie template, and recursing cleanly with backtracking. Nailing this problem proves you can extend a vanilla trie with custom search logic, which is exactly what real autocomplete and spell-correction systems do.

The Core Insight#

The trick is recognising that insertion is identical to a normal trie, while search becomes recursive at every wildcard. Concretely:

1. Build a standard trie keyed on lowercase letters with an isEnd flag.
2. For search, walk the trie character by character.
3. When the current character is a literal letter, follow that single child — fail fast if missing.
4. When the current character is ., recurse into every existing child and return true if any branch succeeds.

The wildcard branching is what turns a single linear walk into a bounded DFS. Because each node has at most 26 children, the worst-case fan-out per dot is 26. The depth is bounded by the word length L, so the worst case is O(26^d times L) where d is the number of dots — fast in practice because the trie is usually sparse and most branches die early.

Visual Dry Run#

After addWord("bad"), addWord("dad"), addWord("mad") the trie looks like this — three sibling branches sharing only the root.

            root
          / |  \
         b  d   m
         |  |   |
         a  a   a
         |  |   |
         d* d*  d*
       (* = isEnd)

Now consider search(".ad"):

Step 1: ch = '.', recurse into every child of root → b, d, m
Step 2 (b-branch): ch = 'a', b has child a → continue
Step 3 (b-branch): ch = 'd', a has child d, d.isEnd = true → return TRUE

The first branch succeeds and the recursion short-circuits — we never even explore the d-branch or m-branch. That early termination is what makes the wildcard variant practical even with large dictionaries.

For search("b..") we descend to the b-node, then on the first dot we try every child of b (only a exists), and on the second dot we try every child of a (only d). d.isEnd is true, so the answer is true.

Solution (Optimal) — Trie + DFS#

Python#

class TrieNode:
    __slots__ = ("children", "is_end")
    def __init__(self):
        self.children = {}      # char -> TrieNode
        self.is_end = False     # marks a complete word
 
class WordDictionary:
    def __init__(self):
        self.root = TrieNode()
 
    def addWord(self, word: str) -> None:
        # Standard trie insert — O(L) per word
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True
 
    def search(self, word: str) -> bool:
        # DFS that branches on '.'
        def dfs(i: int, node: TrieNode) -> bool:
            if i == len(word):
                return node.is_end
            ch = word[i]
            if ch == ".":
                # Wildcard — try every existing child
                for child in node.children.values():
                    if dfs(i + 1, child):
                        return True
                return False
            # Literal char — single branch
            if ch not in node.children:
                return False
            return dfs(i + 1, node.children[ch])
 
        return dfs(0, self.root)

JavaScript#

class TrieNode {
  constructor() {
    this.children = new Map();
    this.isEnd = false;
  }
}
 
class WordDictionary {
  constructor() {
    this.root = new TrieNode();
  }
 
  addWord(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(ch);
    }
    node.isEnd = true;
  }
 
  search(word) {
    const dfs = (i, node) => {
      if (i === word.length) return node.isEnd;
      const ch = word[i];
      if (ch === ".") {
        // Branch into every child for wildcard
        for (const child of node.children.values()) {
          if (dfs(i + 1, child)) return true;
        }
        return false;
      }
      const next = node.children.get(ch);
      if (!next) return false;
      return dfs(i + 1, next);
    };
    return dfs(0, this.root);
  }
}

Complexity#

• addWord: O(L) time, O(L) extra space per new node created.
• search worst case: O(26^d times L) where d is the number of dots. With no dots it is O(L).
• Total space: O(N times L) for N words of average length L.

Common Mistakes#

1. Returning true on missing wildcard child — When the current node has zero children at a ., you must return false, not true. The dot still requires some letter to match.
2. Iterating with for-loop over 26 letters when using a Map — If you store children in a hash map, only iterate the existing children. Iterating all 26 letters and checking has works but wastes time on dead branches.
3. Forgetting isEnd at recursion base case — The base i == len(word) must check node.is_end, not just return true. Otherwise search("ba") would match "bad".
4. Mutating the trie inside search — Some candidates accidentally write node.children[ch] = TrieNode() inside search. Search must never modify the trie.
5. Not handling repeated calls efficiently — Building a fresh trie inside the search function instead of reusing self.root makes every search O(N times L). Build once, query many.
6. Using arrays of size 26 then iterating null slots — Acceptable for memory but be aware that worst-case wildcard fan-out still scans 26 slots per dot.

Interview Tips#

• State the trie structure first, then the wildcard recursion. Interviewers value seeing the design before the code.
• Explicitly mention that addWord is unchanged from LC 208 — this signals you recognise the pattern.
• Walk through complexity in two cases — no dots and all dots — to show you understand the branching factor.
• If the interviewer asks for the worst case bound, say O(26^d times L) and explain why the constraint of 2 dots makes it cheap in practice.
• Mention iterative BFS as an alternative to recursion if stack depth is a concern, although recursion is cleaner and rarely deep enough to matter for L up to 25.

Follow-up Questions#

• What if the dictionary contains millions of words? The trie compresses common prefixes, so memory grows sub-linearly. For extreme scale, consider a compressed trie (radix tree) or a DAWG.
• How would you support * (zero or more characters)? That turns it into a regex matcher — recurse with two transitions per *, advance pattern only and advance both. See LC 10 Regular Expression Matching.
• What about deletion? Walk down marking the path, clear isEnd, then unlink nodes bottom-up that have no children and no isEnd.
• Can you make search iterative? Yes — use a queue or stack of (node, index) pairs. BFS gives a level-by-level wildcard expansion.
• How would you return all matches instead of a boolean? Continue the DFS even after finding a match and collect words by tracking the path string.

Key Takeaways#

• A trie plus DFS handles wildcard search elegantly — literal characters follow one child, dots fan out to all children.
• addWord is the standard LC 208 insert; only search changes.
• Worst-case search is O(26^d times L) where d is the number of dots, but pruning makes it fast in practice.
• Always check isEnd at the recursion base — never return true just for reaching depth L.
• This is the canonical FAANG trie-with-twist problem; mastering it sets you up for word search II, autocomplete, and stream-of-characters.
• The pattern generalises: any time a search query has flexibility, recurse over the trie and branch only where needed.