-
Notifications
You must be signed in to change notification settings - Fork 257
/
add-and-search-word.cpp
58 lines (51 loc) · 1.6 KB
/
add-and-search-word.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
// Time: O(min(n, h)), per operation
// Space: O(min(n, h))
class WordDictionary {
public:
struct TrieNode {
bool isString = false;
unordered_map<char, TrieNode *> leaves;
};
WordDictionary() {
root_ = new TrieNode();
root_->isString = true;
}
// Adds a word into the data structure.
void addWord(string word) {
auto* p = root_;
for (const auto& c : word) {
if (p->leaves.find(c) == p->leaves.cend()) {
p->leaves[c] = new TrieNode;
}
p = p->leaves[c];
}
p->isString = true;
}
// Returns if the word is in the data structure. A word could
// contain the dot character '.' to represent any one letter.
bool search(string word) {
return searchWord(word, root_, 0);
}
bool searchWord(string word, TrieNode *node, int s) {
if (s == word.length()) {
return node->isString;
}
// Match the char.
if (node->leaves.find(word[s]) != node->leaves.end()) {
return searchWord(word, node->leaves[word[s]], s + 1);
} else if (word[s] == '.') { // Skip the char.
for (const auto& i : node->leaves) {
if (searchWord(word, i.second, s + 1)) {
return true;
}
}
}
return false;
}
private:
TrieNode *root_;
};
// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary;
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");