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: Design a data structure that stores words and supports two operations: addWord and search. The search query may contain the wildcard character ., which can match any single letter. The challenge is handling these wildcard queries efficiently while keeping insert operations fast.
Approach 1: Trie Data Structure with DFS (Time: O(m) add, O(26^k * m) search, Space: O(N * m))
The most common solution uses a Trie. Each node represents a character and contains children for the next letters plus a flag marking the end of a word. Inserting a word simply walks through the trie and creates nodes as needed, which takes O(m) time for a word of length m. Searching is straightforward until you encounter a .. At that point you recursively try all possible children using Depth-First Search. This branching handles wildcard matches while still pruning impossible paths quickly. In practice this is fast and scales well for large dictionaries.
Approach 2: HashMap with DFS for Wildcards (Time: O(m) add, O(n * m) worst-case search, Space: O(N * m))
A simpler design stores words grouped by length using a hash map where the key is the word length and the value is a list of words. The addWord operation appends the word to the corresponding bucket. For search, retrieve all words of the same length and compare them character by character. When the query contains ., treat that position as a match for any character. This method relies on brute-force comparison and often scans many candidates, but it is easy to implement and demonstrates the wildcard matching logic clearly. The approach heavily uses string comparison.
Approach 3: Backtracking over Trie Paths (Time: O(26^k * m), Space: O(N * m))
This variation still uses a trie but expresses the wildcard logic explicitly with backtracking. When a normal character appears, move to the corresponding child node. When a . appears, recursively explore every child node from that point. The recursion continues until either the query is fully consumed or all branches fail. The branching factor depends on how many wildcards appear (k), which leads to the 26^k upper bound. The structure remains efficient because most branches terminate early.
Recommended for interviews: The trie-based solution is the expected answer. Interviewers want to see that you recognize prefix-based storage and handle wildcard search using DFS or backtracking. A brute-force hashmap approach shows the baseline idea, but the trie demonstrates strong data structure design and efficient query handling.
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.
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.
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.
Java
C
C++
C#
JavaScript
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.
Java
C
C++
C#
JavaScript
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. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Trie with DFS | Add: O(m), Search: O(26^k * m) | O(N * m) | Best general solution for frequent wildcard queries |
| HashMap by Word Length | Add: O(m), Search: O(n * m) | O(N * m) | Simple implementation when dataset is small |
| Trie with Backtracking | O(26^k * m) | O(N * m) | When handling many wildcard characters efficiently |
Design Add and Search Words Data Structure - Leetcode 211 - Python • NeetCode • 123,196 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 FleetCodePractice this problem
Open in Editor