Practice Design Add and Search Words Data Structure
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Design Add and Search Words Data Structure
Problem Statement
Implement WordDictionary(), addWord(word), and search(pattern). addWord stores a lowercase word. search returns whether a stored word of the same length matches the pattern. Each dot in a pattern stands for exactly one arbitrary letter; other characters must match literally. Practice approach: Use a trie with an end-of-word marker. During search, a literal follows one child; a dot explores every existing child at that node. Accept only after consuming the complete pattern at a terminal node. Wildcards can branch, so search is not always linear in the pattern length.
Source: Design Add and Search Words Data Structure on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
WordDictionary(); addWord("cat"); addWord("cut"); search("c.t"); search("c."); search("dog")[null,null,null,true,false,false]
The dot matches one letter, so c.t matches both stored words but c. has the wrong length.
Constraints
How to solve Design Add and Search Words Data Structure
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
Because stored words live in a trie, a dot never scans the alphabet blindly; it fans out only to children that exist, and with at most two dots per pattern that fan-out is a bounded constant over an exact lookup.
Why brute force is not enough
Keeping words in a list and matching each against the pattern costs O(total stored characters) per search; with up to 10000 calls and words up to 25 letters that approaches 2.5 * 10^9 comparisons even when bucketed by length.
Approach
- Store words in a trie whose nodes hold up to 26 child links and an end-of-word flag; addWord walks or creates one node per character and flags the last node.
- Implement search as a recursive match over a node and a pattern position, with the invariant that the pattern prefix before that position is spelled by the root-to-node path.
- At a literal, follow the single matching child or fail this branch; at a dot, try every existing child and succeed if any leads to a full match.
- When the position reaches the pattern's end, return the node's end flag; merely existing is not enough because the node may be a prefix of longer words.
Walkthrough of Example 1
WordDictionary(); addWord("cat"); addWord("cut"); search("c.t"); search("c."); search("dog") → [null,null,null,true,false,false]
- addWord(cat) creates the path c, a, t and flags t; addWord(cut) reuses c, then creates u and a second flagged t.
- search(c.t): c moves to the c node; the dot tries child a, and the literal t reaches a flagged node, so the answer is true.
- search(c.): after c, the dot reaches a or u, but the pattern ends at nodes whose flag is false, so the answer is false.
- search(dog): the root has no d child, so the search fails immediately with false.
- The call sequence produces [null,null,null,true,false,false], matching the expected output.
Time and space
Time O(L) per addWord, O(26^d * L) per search · Space O(N * L). L is the word or pattern length, N the number of stored words, and d the dot count (at most 2); a search visits at most 26^2 times the nodes of an exact lookup, and the trie holds at most one node per inserted character.
Interview pitfalls
- Returning true when the pattern ends at any existing node; storing cat creates a node for ca, yet search(ca) must be false.
- Treating a dot as matching zero or several characters; it consumes exactly one trie edge, so c. can never match cat.
- Looping over all 26 letters at a dot instead of only existing children, a large constant-factor waste.
- Combining the dot's child results incorrectly, for example returning only the last child's result so an early true is lost.
Follow-up questions interviewers ask
- How would the design change if patterns allowed unlimited dots, or a star matching any sequence of letters?
- How would you support deleting a word while reclaiming trie branches no other word uses?
Further reading on the technique: Trie
Related LeetCode Problems
Practice more problems similar to Design Add and Search Words Data Structure.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.