blob: b56e38b6a2e3a8d4c314719c1e996e4f4789f117 (
plain)
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
|
// 208. Implement Trie (Prefix Tree)
#include "leetcode.h"
class Trie {
public:
Trie() {}
void insert(string word) {
Trie *node = this;
for (char c : word) {
if (!node->next.count(c))
node->next[c] = new Trie();
node = node->next[c];
}
node->is_word = true;
}
bool search(string word) {
Trie *node = this;
for (char c : word) {
if (!node->next.count(c))
return false;
node = node->next[c];
}
return node->is_word;
}
bool startsWith(string prefix) {
Trie *node = this;
for (char c : prefix) {
if (!node->next.count(c))
return false;
node = node->next[c];
}
return true;
}
private:
map<char, Trie *> next = {};
bool is_word = false;
};
int main() {
Trie *obj = new Trie();
obj->insert("Trie");
bool param_2 = obj->search("Trie");
bool param_3 = obj->startsWith("Trie");
}
|