字典树（Trie）是一种树形数据结构，用于高效地存储和检索字符串数据集。
1
2
3
4
5
6
7
8
9
10
| struct TrieNode {
TrieNode* children[26];
bool isEnd;
TrieNode() : isEnd(false) {
for (int i = 0; i < 26; i++) {
children[i] = nullptr;
}
}
};
|
1
2
3
4
5
6
7
8
9
10
| void insert(string word) {
TrieNode* node = root;
for (char c : word) {
if (!node->children[c - 'a']) {
node->children[c - 'a'] = new TrieNode();
}
node = node->children[c - 'a'];
}
node->isEnd = true;
}
|
1
2
3
4
5
6
7
8
9
10
| bool search(string word) {
TrieNode* node = root;
for (char c : word) {
if (!node->children[c - 'a']) {
return false;
}
node = node->children[c - 'a'];
}
return node->isEnd;
}
|
1
2
3
4
5
6
7
8
9
10
| bool startsWith(string prefix) {
TrieNode* node = root;
for (char c : prefix) {
if (!node->children[c - 'a']) {
return false;
}
node = node->children[c - 'a'];
}
return true;
}
|