Design a data structure that supports adding new words and finding if a string matches any previously added string.
Implement the WordDictionary class:
WordDictionary() Initializes the object.void addWord(word) Adds word to the data structure, it can be matched later.bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.
Example:
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 <= 25word in addWord consists of lowercase English letters.word in search consist of '.' or lowercase English letters.2 dots in word for search queries.104 calls will be made to addWord and search.Problem Overview: Build a data structure that supports two operations: addWord(word) to store a word and search(pattern) to check if any stored word matches the pattern. The search pattern may include the wildcard ., which matches any single character.
Approach 1: HashMap with DFS for Wildcards (Time: add O(m), search O(n * 26^w), Space: O(n*m))
Store words grouped by length using a HashMap<length, List<word>>. During search, only compare words of the same length as the query. Iterate through each candidate word and check character-by-character, treating . as a match for any character. This approach avoids scanning irrelevant lengths but still requires scanning many candidates when the dictionary grows. It works well for small datasets but degrades when many words share the same length.
Approach 2: Backtracking with Pattern Matching (Time: worst case O(26^w * m), Space: O(m) recursion)
During search, recursively explore possible character matches whenever a . appears. Each wildcard branches into multiple possibilities, effectively performing backtracking over possible character substitutions. This technique demonstrates how wildcard matching works conceptually, but without a specialized structure it repeatedly scans strings and becomes inefficient as the dataset grows. It mainly serves as an intermediate idea before introducing a trie.
Approach 3: Trie Data Structure with DFS (Time: add O(m), search average O(m), worst O(26^w * m), Space: O(n*m))
Insert each word into a Trie, where each node represents a character. addWord simply iterates through characters and creates nodes if missing. For search, traverse the trie normally until encountering .. When a wildcard appears, run a DFS across all child nodes and continue matching the remaining characters. This structure drastically prunes the search space because only valid prefixes are explored. The trie efficiently supports prefix traversal and wildcard branching while keeping operations proportional to the word length.
Recommended for interviews: The trie-based solution is what interviewers expect. It shows you understand prefix trees, branching search with DFS, and how to optimize wildcard pattern matching. Mentioning the naive length-bucket scan demonstrates baseline reasoning, but implementing the trie shows strong command of string indexing and data structure design.
This approach involves using a Trie data structure, which is highly efficient for dynamic prefix search operations. Each node of the Trie represents a character of a string. For the search operation, if the current character is a dot '.', then recursively search all possible nodes. This allows the Trie to handle strings with wildcard characters.
The Python implementation initializes a Trie structure with a root node. addWord iterates through the characters of the word and constructs nodes if they do not exist. search checks each character. When it encounters a '.', it branches out recursively to all children nodes. This efficiently handles wildcard searches.
Python
Time Complexity: O(n) for addWord and O(m^26) in the worst case for search where m is the length of the word.
Space Complexity: O(total_characters) for the trie structure.
This approach uses a combination of a HashMap (Dictionary in some languages) to store words based on their lengths. The search checks the word's length first and retrieves potential matches. For wildcards, a Depth-First Search (DFS) explores possible character matches sequentially.
The Java solution uses a HashMap to categorize words by their length, providing O(1) access to words of the same size during the search. The DFS-like isMatch function is straightforward, checking corresponding positions of candidate words and query words. It allows efficient handling of the '.' wildcard.
Java
Time Complexity: O(m*n) for search, where m is the number of words of the same length and n is the length of the word.
Space Complexity: O(total_chars) for storing words in the HashMap.
Tries, also known as prefix trees, are efficient for searching words by prefixes and can be adapted to handle wildcard characters. In this approach:
The Python code defines a WordDictionary class using a TrieNode class for node representation. The addWord function inserts a word into the trie. The search function handles '.' using a recursive DFS approach, allowing branching wherever a dot is encountered.
Time Complexity: O(n) for adding a word and average of O(n*m) for searching a word, where n is the length of the word and m is the branching factor of the trie. Space Complexity: O(n*m) for storing words in the trie.
In this approach, we utilize backtracking for the search operation. This approach is simpler in terms of implementation but may not be as efficient as using a Trie due to repetitive computations:
addWord function, simply add the word to the list.search function, iterate through each stored word, and use recursion to handle '.' in the search query, comparing matching paths or using any letter at wildcard positions.The Python solution implements WordDictionary using a list to store words. The addWord method appends words to the list, and search checks each word for matching pattern lengths and characters or wildcards using helper function.
Time Complexity: O(m * n) for search, where m is the number of words and n is the average length of the longest word. Space Complexity: O(t * l) for the list, where t is the total words stored, and l is their average length.
| Approach | Complexity |
|---|---|
| Approach 1: Trie-based Implementation | Time Complexity: O(n) for addWord and O(m^26) in the worst case for search where m is the length of the word. |
| Approach 2: HashMap with DFS for Wildcards | Time Complexity: O(m*n) for search, where m is the number of words of the same length and n is the length of the word. |
| Approach 1: Using Trie Data Structure | Time Complexity: O(n) for adding a word and average of O(n*m) for searching a word, where n is the length of the word and m is the branching factor of the trie. Space Complexity: O(n*m) for storing words in the trie. |
| Approach 2: Backtracking | Time Complexity: O(m * n) for search, where m is the number of words and n is the average length of the longest word. Space Complexity: O(t * l) for the list, where t is the total words stored, and l is their average length. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap by Word Length | Add: O(m), Search: O(n*m) | O(n*m) | Simple implementation when dataset is small and wildcard searches are rare |
| Backtracking Pattern Match | Worst O(26^w * m) | O(m) | Conceptual wildcard exploration without building specialized structures |
| Trie with DFS | Add: O(m), Search: avg O(m), worst O(26^w * m) | O(n*m) | Best general solution for frequent searches and wildcard queries |
Design Add and Search Words Data Structure - Leetcode 211 - Python • NeetCode • 151,201 views views
Watch 9 more video solutions →Practice Design Add and Search Words Data Structure with our built-in code editor and test cases.
Practice on FleetCode