LeetCode 208. Implement Trie (Prefix Tree)

前言

我第一次知道Trie,是因为之前写ACBM算法。
题目也挺直白的,直接上代码吧。

代码实现

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
class Node {
public:
vector<Node*> children;
char val;
bool end;
Node(char val) {
this -> val = val;
this -> end = false;
this -> children = vector<Node*>(26, NULL);
}

void insert(string str) {
if (str.size() == 0) {
this -> end = true;
return;
}
char c = str[0];
if (this -> children[c-'a'] == NULL) {
children[c-'a'] = new Node(c);
}
this -> children[c-'a'] -> insert(str.substr(1, str.size() -1));
}

bool search(string str, bool prefix) {
if (str.size() == 0) {
if (prefix) return true;
else {
return this -> end;
}
}
char c = str[0];
if (this -> children[c-'a'] == NULL) return false;
return this -> children[c-'a'] -> search(str.substr(1, str.size() -1), prefix);
}
};

class Trie {
public:
Node *root;
/** Initialize your data structure here. */
Trie() {
this -> root = new Node('0');
}

/** Inserts a word into the trie. */
void insert(string word) {
this -> root -> insert(word);
}

/** Returns if the word is in the trie. */
bool search(string word) {
return this -> root -> search(word, false);
}

/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
return this -> root -> search(prefix, true);
}
};