forked from mdmzfzl/NeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
0211-design-add-and-search-words-data-structure.cpp
174 lines (139 loc) · 5.47 KB
/
0211-design-add-and-search-words-data-structure.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
/*
Problem: LeetCode 211 - Design Add and Search Words Data Structure
Description:
Design a data structure that supports adding new words and finding if a string matches any previously added string.
The word may contain only lowercase alphabets '.' or be an empty string.
Intuition:
To solve this problem, we can use a Trie data structure to store the words. The Trie allows efficient insertion and search operations. For the '.' character, we need to consider all possible characters at that position.
Approach:
1. TrieNode:
- Define a TrieNode class that represents each node in the Trie.
- Each TrieNode has an array of pointers to child nodes, representing the lowercase alphabets and the '.' character.
- Each TrieNode also has a boolean flag to indicate if it represents a complete word.
2. WordDictionary:
- Define a WordDictionary class that contains the root of the Trie.
- Implement the addWord method to add a word to the Trie:
- Start from the root and iterate over each character in the word.
- For each character, check if the corresponding child node exists. If not, create a new node and link it to the current node.
- Move to the child node and repeat the process for the next character.
- After iterating through all characters, mark the last node as a complete word.
- Implement the search method to search for a word in the Trie:
- Start from the root and iterate over each character in the word.
- For each character, check if the corresponding child node exists. If not, return false.
- Move to the child node and repeat the process for the next character.
- After iterating through all characters, check if the last node represents a complete word.
- Implement the searchWithWildcard method to search for a word with wildcard characters ('.') in the Trie:
- Use a recursive approach to search for the word.
- If the current character is a wildcard ('.'), iterate over all possible child nodes and recursively search for the remaining word.
- If the current character is not a wildcard, check if the corresponding child node exists and recursively search for the remaining word.
- Return true if any of the recursive searches return true.
- Return false if no matching word is found.
Time Complexity:
- Adding a word: O(m), where m is the length of the word being added.
- Searching a word: O(m), where m is the length of the word being searched.
- Searching a word with wildcard: O(n*m), where n is the number of words in the Trie and m is the length of the word being searched.
Space Complexity:
- The space complexity is O(n*m), where n is the number of words added to the Trie and m is the average length of the words.
*/
class TrieNode {
public:
bool isWord;
TrieNode *children[26];
TrieNode() {
isWord = false;
for (int i = 0; i < 26; i++) {
children[i] = nullptr;
}
}
};
class WordDictionary {
private:
TrieNode *root;
public:
WordDictionary() {
root = new TrieNode();
}
void addWord(string word) {
TrieNode *node = root;
for (char c : word) {
int index = c - 'a';
if (!node->children[index]) {
node->children[index] = new TrieNode();
}
node = node->children[index];
}
node->isWord = true;
}
bool search(string word) {
return searchHelper(word, root, 0);
}
bool searchHelper(string word, TrieNode *node, int index) {
if (index == word.length()) {
return node->isWord;
}
char c = word[index];
if (c != '.') {
int childIndex = c - 'a';
if (node->children[childIndex]) {
return searchHelper(word, node->children[childIndex], index + 1);
} else {
return false;
}
} else {
for (int i = 0; i < 26; i++) {
if (node->children[i] && searchHelper(word, node->children[i], index + 1)) {
return true;
}
}
return false;
}
}
};
/*
class WordDictionary {
private:
struct TrieNode {
TrieNode* child[26];
bool isWord;
TrieNode() {
for(auto &i: child)
i = nullptr;
isWord = false;
}
};
TrieNode* root;
bool searchInNode(string& word, int i, TrieNode* node) {
if (node == NULL)
return false;
if (i == word.size())
return node->isWord;
// if its an alphabet and not .
if (word[i] != '.')
return searchInNode(word, i + 1, node->child[word[i] - 'a']);
// If the current character is a dot, we need to check all children of the current node
// recursively by skipping over the dot character and moving to the next character of the word
for (int j = 0; j < 26; j++)
if (searchInNode(word, i + 1, node->child[j]))
return true;
return false;
}
public:
WordDictionary() {
root = new TrieNode();
}
void addWord(string word) {
TrieNode *current = root;
for(auto c: word) {
int i = c - 'a';
if(!current->child[i])
current->child[i] = new TrieNode();
current = current->child[i];
}
current->isWord = true;
}
bool search(string word) {
TrieNode* node = root;
return searchInNode(word, 0, node);
}
};
*/