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 | class Trie {
public:
static constexpr int CHILDSIZE = 26;
bool isWord;
string word;
Trie* child[CHILDSIZE];
Trie() {
isWord = false;
for (int i = 0; i < CHILDSIZE; i++)
this->child[i] = nullptr;
}
void insert(string s) {
Trie *node = this;
for (auto &chr : s) {
int idx = chr - 'a';
if (!node->child[idx])
node->child[idx] = new Trie();
node = node->child[idx];
}
node->isWord = true;
node->word = s;
}
bool search(string word) {
if (word.empty())
return this->isWord;
if (word[0] == '.') {
for (int i = 0; i < CHILDSIZE; i++)
if (this->child[i])
if (this->child[i]->search(word.substr(1)))
return true;
return false;
}
int idx = word[0] - 'a';
if (!this->child[idx])
return false;
return this->child[idx]->search(word.substr(1));
}
};
class WordDictionary {
private:
Trie* trie;
public:
WordDictionary() {
this->trie = new Trie();
}
void addWord(string word) {
this->trie->insert(word);
}
bool search(string word) {
return this->trie->search(word);
}
};
/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary* obj = new WordDictionary();
* obj->addWord(word);
* bool param_2 = obj->search(word);
*/
|