Add and Search Words LeetCode 211 — Trie

LeetCode 211 Design Add and Search Words asks you to implement a WordDictionary class that supports two operations: addWord(word) inserts a word string into the data structure, and search(word) returns true if there is any string in the data structure that matches word. The twist is that word in search may contain dots — each dot can match any single letter. For example, if "bad" and "dad" and "mad" are all added, then search("pad") returns false, search("bad") returns true, and search(".ad") returns true because the dot can match b, d, or m.

The challenge is designing a data structure that handles both exact-match lookups and wildcard-pattern lookups efficiently. The dot character is a single-character wildcard, similar to the regex dot. The problem guarantees that word in addWord consists of lowercase English letters only, and word in search consists of lowercase English letters or dots. Each word has length between 1 and 25, and at most 10,000 calls will be made to addWord and search combined.

This is a classic data structure design problem that appears frequently in FAANG interviews because it tests both Trie knowledge and recursive DFS with backtracking. The naive approach using a hash set breaks down immediately when wildcards are introduced, and the correct solution — a Trie with DFS — elegantly handles both exact and pattern-based lookups by exploiting the character-by-character structure of the Trie.

The simplest data structure for storing words is a hash set. Inserting a word into a hash set is O(m) where m is the word length — you just hash the string and store it. For exact-match search with no wildcards, a hash set gives O(m) lookup as well — hash the query and check membership. This approach handles addWord trivially and handles search perfectly when no dots are present.

The problem falls apart when the search pattern contains dots. If you store all words in a hash set and receive a query like ".ad", you cannot hash it directly because the dot could expand to any of 26 letters. You would have to generate all 26 candidate strings ("aad", "bad", "cad", ..., "zad") and check each one, costing O(26 * m) per dot. For a pattern with k dots that is a string of length m, you would need up to O(26^k) hash lookups. In the worst case — a pattern like "....." with all dots — you check O(26^m) candidates, the same as brute force.

Even grouping words by length does not help enough. Scanning all words of the same length and comparing character by character costs O(n * m) where n is the number of stored words of that length — up to O(10000 * 25) = O(250,000) per search call. A Trie provides structured traversal that lets you skip entire subtrees when a character position does not match, dramatically reducing work in practice even though the asymptotic worst case remains exponential for all-dot queries.

A Trie (prefix tree) is a tree where each node represents a character prefix. The root represents the empty string. Each edge from a parent to a child represents appending one character. Every path from root to a node marked with isEnd = true spells out a word that was inserted. For this problem, since all characters are lowercase English letters, each node needs exactly 26 potential children — one per letter a through z.

The TrieNode class has two fields: children, an array or dictionary mapping characters to child TrieNodes, and isEnd, a boolean flag that marks whether this node is the end of an inserted word. In Python, children is typically a dict keyed by character or a list of 26 elements indexed by ord(c) - ord("a"). In Java, children is a TrieNode[26] array. The isEnd flag is false by default and is set to true when addWord finishes inserting all characters of a word.

The addWord operation is a simple O(m) traversal. Start at the root. For each character in the word, compute the child index (for a list: ord(c) - ord("a"), for a dict: c directly). If the child at that index is None or null, create a new TrieNode. Move the current pointer to that child. After processing all characters, set isEnd = true on the final node. The total work is O(m) per insert with O(m) space for nodes that do not already exist from a previously inserted word sharing the same prefix.

The search operation uses a recursive DFS helper that takes a node and the remaining suffix of the query pattern. The base case: when the suffix is empty, return node.isEnd — if we have consumed all characters in the pattern and the current node marks the end of a word, the match succeeds. The recursive case has two branches depending on whether the current character is a dot or a letter.

For a normal letter character c, the search is deterministic: look up the child of the current node corresponding to c. If no such child exists, return false immediately (branch pruning). If the child exists, recurse on that child with the remaining suffix (pattern[1:]). For a dot character, the search is non-deterministic: iterate over all 26 possible children of the current node. For each non-null child, recurse on that child with the remaining suffix. If any recursive call returns true, immediately return true (short-circuit). If all children return false or all children are null, return false.

The DFS ensures that every possible interpretation of dot characters is explored, but branching only happens at dot positions. For exact characters, only one branch is followed, so those positions cost O(1) each. The total work is proportional to O(26^d) where d is the number of dot characters in the query, multiplied by the length of non-dot substrings traversed. For typical queries with a few dots scattered among letters, the actual number of nodes visited is much smaller than 26^m.

The most impactful optimization is storing words grouped by length inside the Trie or alongside it. Since a dot matches exactly one character, a query of length m can only match stored words of exactly length m. By maintaining a dict mapping word-length to a sub-Trie or set, the search can immediately skip all Trie branches that would lead to words of wrong length. This early-length pruning is particularly effective when word lengths vary widely across addWord calls.

Within the Trie itself, you can further prune by maintaining a count of how many complete words pass through each node (a "word count" field). If a Trie node has zero words below it, it is useless to recurse into it. This approach converts the DFS from a pure depth-first tree walk into a guided walk that skips barren subtrees. It adds O(m) overhead per addWord to update counts along the insertion path but pays dividends during search by skipping empty branches.

In practice, the standard TrieNode with a dict (Python) or TrieNode[26] array (Java) paired with a simple recursive DFS is fast enough for LeetCode 211 without extra optimizations. The branching factor at each dot position is bounded by the actual number of non-null children, not 26. Interview interviewers primarily look for correct Trie structure and correct DFS logic — mention length grouping and count-based pruning as bonus optimizations to demonstrate depth of understanding.

The Python implementation uses a dict-based TrieNode. TrieNode has __init__ setting self.children = {} and self.is_end = False. WordDictionary.__init__ sets self.root = TrieNode(). addWord iterates over each character c in word: if c not in cur.children, cur.children[c] = TrieNode(); then cur = cur.children[c]; after the loop, cur.is_end = True. The search method calls a helper _dfs(node, word, i) where i is the current index. Base case: if i == len(word), return node.is_end. If word[i] is a dot: return any(_dfs(child, word, i+1) for child in node.children.values()). Else: c = word[i]; if c not in node.children, return False; return _dfs(node.children[c], word, i+1).

The Java implementation uses a TrieNode class with TrieNode[] children = new TrieNode[26] and boolean isEnd = false. addWord iterates with int idx = c - "a"; if root.children[idx] == null, create new TrieNode; cur = cur.children[idx]; after the loop, cur.isEnd = true. The search method calls a private boolean dfs(TrieNode node, String word, int i). Base case: if i == word.length(), return node.isEnd. char c = word.charAt(i); if c == ".": for (TrieNode child : node.children) { if (child != null && dfs(child, word, i+1)) return true; } return false; else: int idx = c - "a"; if (node.children[idx] == null) return false; return dfs(node.children[idx], word, i+1).

Common implementation pitfalls: (1) using a list instead of a dict in Python and forgetting to initialize it with 26 None values; (2) in Java, iterating over node.children without null-checking each element; (3) returning node != null instead of node.isEnd at the base case — the node existing means a prefix exists, not that a complete word exists; (4) incrementing i before the recursive call, which shifts indices incorrectly — always pass i+1 as the next position without modifying i.

Word Search II (LeetCode 212) combines a Trie with a grid DFS. You build a Trie from all target words and then do a DFS over a 2D character grid, traversing the Trie simultaneously to detect when you have traced a complete word path on the board. The Trie allows early termination when the current grid path diverges from all remaining target words, making it far more efficient than running a separate DFS for each word individually.

Implement Trie (LeetCode 208) is the foundational problem for this topic — it asks you to implement insert, search, and startsWith without any wildcards. Mastering LeetCode 208 first gives you the clean Trie skeleton that LeetCode 211 then extends with DFS wildcard search. Replace Words (LeetCode 648) uses a Trie of root words to replace words in a sentence with their shortest matching root prefix, demonstrating how Trie traversal can efficiently find the lexicographically smallest matching prefix.

The broader Trie family includes Auto-Complete System (LeetCode 642), Search Suggestions System (LeetCode 1268), and Stream of Characters (LeetCode 1032). Each applies Trie traversal in a slightly different context — ranking completions, grouping suggestions, or matching patterns from a continuous stream of characters. All share the same core TrieNode with children and isEnd, and all benefit from understanding the DFS pattern introduced in LeetCode 211.