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.The key idea behind #211 Design Add and Search Words Data Structure is to store words in a Trie (prefix tree). A Trie efficiently supports prefix-based operations and allows character-by-character traversal. When adding a word, each character is inserted into the Trie, creating nodes as needed and marking the final node as the end of a word.
The challenge appears during search because the query may contain the wildcard character ., which can represent any letter. To handle this, we use Depth-First Search (DFS). When encountering a normal character, we simply move to the corresponding child node. When encountering ., we recursively explore all possible child nodes at that level.
This combination of Trie for storage and DFS for wildcard matching allows efficient queries while avoiding scanning every stored word. The search complexity depends on the number of wildcard branches explored, while insert operations remain linear with respect to the word length.
| Operation | Approach | Time Complexity | Space Complexity |
|---|---|---|---|
| Add Word | Trie Insertion | O(L) | O(L) |
| Search Word (no wildcard) | Trie Traversal | O(L) | O(1) |
| Search Word (with '.') | Trie + DFS Branching | O(26^L) worst-case | O(L) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
You should be familiar with how a Trie works. If not, please work on this problem: <a href="https://leetcode.com/problems/implement-trie-prefix-tree/">Implement Trie (Prefix Tree)</a> first.
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.
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.
1class TrieNode:
2 def __init__(self):
3 self.children = {}
4 self.is_end_of_word = False
5
6class WordDictionary:
7 def __init__(self):
8 self.root = TrieNode()
9
10 def addWord(self, word: str) -> None:
11 node = self.root
12 for char in word:
13 if char not in node.children:
14 node.children[char] = TrieNode()
15 node = node.children[char]
16 node.is_end_of_word = True
17
18 def search(self, word: str) -> bool:
19 def search_in_node(word, node):
20 for i, char in enumerate(word):
21 if char == '.':
22 for child in node.children.values():
23 if search_in_node(word[i + 1:], child):
24 return True
25 return False
26 else:
27 if char not in node.children:
28 return False
29 node = node.children[char]
30 return node.is_end_of_word
31 return search_in_node(word, self.root)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.
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.
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.
1import java.util.*;
2
3class WordDictionary {
Tries, also known as prefix trees, are efficient for searching words by prefixes and can be adapted to handle wildcard characters. In this approach:
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.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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The '.' character can represent any single letter. When encountered during search, the algorithm explores all possible child nodes from the current Trie node using DFS to check if any path forms a valid word.
Yes, Trie-based design problems like this are commonly asked in FAANG and other top tech company interviews. They test knowledge of data structures, recursion, and efficient search strategies.
A Trie (prefix tree) is the best data structure for this problem. It allows fast insertion and efficient character-by-character traversal, which is especially useful when handling wildcard searches.
The optimal approach uses a Trie data structure combined with Depth-First Search. The Trie stores characters efficiently, while DFS helps explore multiple branches when a wildcard '.' appears in the search query.
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.
1#include <vector>
2using namespace std;
3
4class TrieNode {
5public:
6 vector<TrieNode*> children;
7 bool endOfWord;
8
9 TrieNode() : children(26, nullptr), endOfWord(false) {}
10};
11
12class WordDictionary {
13 TrieNode* root;
14
15public:
16 WordDictionary() {
17 root = new TrieNode();
18 }
19
20 void addWord(string word) {
21 TrieNode* node = root;
22 for (char ch : word) {
23 if (node->children[ch - 'a'] == nullptr) {
24 node->children[ch - 'a'] = new TrieNode();
25 }
26 node = node->children[ch - 'a'];
27 }
28 node->endOfWord = true;
29 }
30
31 bool search(string word) {
32 return searchInNode(word, root);
33 }
34
35private:
36 bool searchInNode(string word, TrieNode* node) {
37 for (int i = 0; i < word.size(); i++) {
38 char ch = word[i];
39 if (ch == '.') {
40 for (TrieNode* child : node->children) {
41 if (child != nullptr && searchInNode(word.substr(i + 1), child)) {
42 return true;
43 }
44 }
45 return false;
46 } else {
47 node = node->children[ch - 'a'];
48 if (node == nullptr) {
49 return false;
50 }
51 }
52 }
53 return node->endOfWord;
54 }
55};This C++ implementation constructs a WordDictionary class using a TrieNode class. Each node has a vector to store children references and a boolean to indicate the end of a word. By handling '.' for wildcard searches using a helper function, it traverses multiple paths.
1#include <string.h>
2#include <stdbool.h>
3#include <stdlib.h>
4#include <stdio.h>
5
6#define MAX_WORDS 10000
7char* wordList[MAX_WORDS];
8int wordCount = 0;
9
10void wordDictionaryAddWord(char* word) {
11 wordList[wordCount++] = strdup(word);
12}
13
14bool isMatch(const char* word, const char* pattern) {
15 for (int i = 0; i < strlen(pattern); i++) {
16 if (pattern[i] != '.' && word[i] != pattern[i]) return false;
17 }
18 return true;
19}
20
21bool wordDictionarySearch(const char* pattern) {
22 for (int i = 0; i < wordCount; i++) {
23 if (strlen(wordList[i]) == strlen(pattern) && isMatch(wordList[i], pattern)) {
24 return true;
25 }
26 }
27 return false;
28}The C implementation uses arrays to store words, with add function copying words into the list. The search function iterates through the list, checking length equality and character pattern matches or wildcards in sequence.