Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。
请你实现 Trie 类：
Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
示例：
输入
[“Trie”, “insert”, “search”, “search”, “startsWith”, “insert”, “search”]
[[], [“apple”], [“apple”], [“app”], [“app”], [“app”], [“app”]]
输出
[null, null, true, false, true, null, true]
解释
Trie trie = new Trie();
trie.insert(“apple”);
trie.search(“apple”); // 返回 True
trie.search(“app”); // 返回 False
trie.startsWith(“app”); // 返回 True
trie.insert(“app”);
trie.search(“app”); // 返回 True
提示：
1 <= word.length, prefix.length <= 2000
word 和 prefix 仅由小写英文字母组成
insert、search 和 startsWith 调用次数 总计 不超过 3 * 10(4) 次
前缀树，节点中存放26个节点，一个标志位isEnd即可
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
| class Trie {
public:
class node {
public:
node *children[26] = {nullptr};
bool isEnd;
node(bool isEnd) : isEnd(isEnd) {}
};
node *root;
Trie() { root = new node(false); }
void insert(string word) {
node *cur = root;
for (char i : word) {
if (cur->children[i - 'a'] == nullptr)
cur->children[i - 'a'] = new node(false);
cur = cur->children[i - 'a'];
}
cur->isEnd = true;
}
node *searchNode(string &word) {
node *cur = root;
for (char i : word) {
if (cur->children[i - 'a'] == nullptr)
return nullptr;
cur = cur->children[i - 'a'];
}
return cur;
}
bool search(string word) {
node *cur = searchNode(word);
if (cur == nullptr)
return false;
return cur->isEnd;
}
bool startsWith(string prefix) {
node *cur = searchNode(prefix);
if (cur == nullptr)
return false;
return true;
}
};
|
或者使用压缩字典树
节点存储：每个节点存一个字符串 path，代表一段压缩后的路径。
分叉逻辑：
如果待插入字符串与当前节点 path 完全匹配，继续向下。
如果部分匹配，则需要在匹配中断处将当前节点分裂成父子两个节点。
子节点管理：使用 std::map<char, Node*>，首字母决定了走哪个分支。
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
| class Trie {
public:
struct Node {
string path;
map<char, Node *> children;
bool isEnd;
Node(string p, bool end) : path(p), isEnd(end) {}
};
Node *root;
int getCommonPrefixLen(const string &s1, const string &s2) {
int i = 0;
while (i < s1.size() && i < s2.size() && s1[i] == s2[i]) {
i++;
}
return i;
}
Trie() { root = new Node("", false); }
void insert(string word) {
Node *curr = root;
string s = word;
while (!s.empty()) {
char firstChar = s[0];
if (curr->children.find(firstChar) == curr->children.end()) {
curr->children[firstChar] = new Node(s, true);
return;
}
Node *child = curr->children[firstChar];
int commonLen = getCommonPrefixLen(child->path, s);
if (commonLen < child->path.size()) {
string suffix = child->path.substr(commonLen);
Node *splitNode = new Node(suffix, child->isEnd);
splitNode->children = move(child->children);
child->path = child->path.substr(0, commonLen);
child->isEnd = false;
child->children.clear();
child->children[suffix[0]] = splitNode;
}
if (commonLen < s.size()) {
s = s.substr(commonLen);
curr = child;
} else {
child->isEnd = true;
return;
}
}
root->isEnd = true;
}
bool search(string word) {
Node *curr = root;
string s = word;
while (!s.empty()) {
char firstChar = s[0];
if (curr->children.find(firstChar) == curr->children.end())
return false;
Node *child = curr->children[firstChar];
if (s.size() < child->path.size() ||
s.substr(0, child->path.size()) != child->path) {
return false;
}
s = s.substr(child->path.size());
curr = child;
}
return curr->isEnd;
}
bool startsWith(string prefix) {
Node *curr = root;
string s = prefix;
while (!s.empty()) {
char firstChar = s[0];
if (curr->children.find(firstChar) == curr->children.end())
return false;
Node *child = curr->children[firstChar];
int commonLen = getCommonPrefixLen(child->path, s);
if (commonLen == s.size())
return true;
if (s.size() < child->path.size() ||
s.substr(0, child->path.size()) != child->path) {
return false;
}
s = s.substr(child->path.size());
curr = child;
}
return true;
}
};
|
