How to Solve Design Add and Search Words Data Structure

This problem requires implementing a WordDictionary that can add new words and search for exact matches or patterns with '.' wildcards. Using a Trie allows efficient storage and traversal of word prefixes. DFS handles wildcard searches by exploring all possible continuations when encountering a '.', ensuring correct matching while keeping operations performant.

Problem Statement

Design a data structure that allows adding words and searching whether a word or pattern exists. Patterns may include '.' which matches any single letter, requiring careful traversal of stored words.

Implement the WordDictionary class with the following methods: addWord(word) adds a word to the dictionary, and search(word) returns true if the exact word or a pattern matches any previously added word. Constraints include words up to 25 letters, lowercase letters, patterns with at most 2 dots, and up to 10^4 calls to addWord and search.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Input ["WordDictionary","addWord","addWord","addWord","search","search","search","search"] [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]] Output [null,null,null,null,false,true,true,true]

Explanation WordDictionary wordDictionary = new WordDictionary(); wordDictionary.addWord("bad"); wordDictionary.addWord("dad"); wordDictionary.addWord("mad"); wordDictionary.search("pad"); // return False wordDictionary.search("bad"); // return True wordDictionary.search(".ad"); // return True wordDictionary.search("b.."); // return True

Constraints

• 1 <= word.length <= 25
• word in addWord consists of lowercase English letters.
• word in search consist of '.' or lowercase English letters.
• There will be at most 2 dots in word for search queries.
• At most 104 calls will be made to addWord and search.

Solution Approach

Use a Trie for efficient prefix storage

Construct a Trie where each node represents a character. Adding a word inserts each character sequentially, marking the final node as an end of a word. This enables O(L) insertion, where L is word length, and supports efficient prefix traversal for searches.

DFS for pattern search with wildcards

When searching, use DFS to traverse the Trie. For normal letters, follow the corresponding child node. For '.', recursively explore all child nodes. Return true if a path matches the word length and ends at a marked word node.

Optimize with early pruning

Terminate DFS early when a path cannot possibly match the word or pattern. Skip branches if the remaining length exceeds possible Trie paths. This reduces unnecessary recursion, especially for patterns with multiple wildcards.

Complexity Analysis

Time complexity depends on word length L and Trie branching; addWord is O(L), search is O(26^k * L) in worst case with k wildcards. Space complexity is O(N*L) for storing N words, considering shared prefixes in Trie nodes.

What Interviewers Usually Probe

• Look for efficient prefix storage and DFS handling of wildcards.
• Check if you handle '.' correctly with recursive exploration.
• Expect awareness of Trie node memory usage and early pruning for performance.

Common Pitfalls or Variants

Common pitfalls

• Not handling '.' correctly can miss valid matches or overcount paths.
• Failing to mark the end of words leads to false positives when searching prefixes.
• Inefficient DFS without pruning may timeout with multiple wildcard searches.

Follow-up variants

• Restrict to exact matches only, removing wildcard support.
• Allow arbitrary number of wildcards instead of a max of 2.
• Implement with a hash map of word lengths for faster lookup without Trie.

How GhostInterview Helps

• Provides clear implementation guidance combining Trie and DFS for wildcard search.
• Highlights common edge cases like '.' handling and end-of-word markers.
• Offers performance hints like pruning DFS paths to avoid unnecessary recursion.

Topic Pages

• String
• Depth-First Search
• Design
• Trie

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the main strategy for the WordDictionary problem?

The main strategy is using a Trie to store words efficiently and DFS to handle search patterns including '.' wildcards.

How do I handle '.' in searches for this problem?

During DFS traversal, treat '.' as a wildcard and explore all child nodes recursively to match any character at that position.

Why is a Trie preferred over a list for this problem?

A Trie allows prefix sharing and O(L) insertions and searches, while a list would require checking every word for matches, which is slower for large datasets.

Can this approach handle multiple '.' wildcards efficiently?

Yes, but each wildcard increases branching in DFS exponentially. Limiting the number of wildcards and pruning invalid paths keeps searches efficient.

Is this problem mainly String plus Depth-First Search pattern?

Yes, it combines string manipulation and DFS traversal over a Trie structure to support pattern matching efficiently.