字典树的基础算法
字典树
字典树是一种树形结构，用于存储字符串集合。它的每个节点代表一个字符，从根节点到某个节点的路径代表一个字符串。字典树可以高效地插入、删除和查找字符串。
字典树的基本操作
-
插入字符串：从根节点开始，依次遍历字符串的每个字符，如果当前节点不存在该字符的子节点，则创建一个新的子节点，并将当前节点指向该子节点。重复这个过程，直到遍历完整个字符串。最后，将当前节点标记为字符串的结尾。
-
查找字符串：从根节点开始，依次遍历要查找的字符串的每个字符。如果当前节点的子节点中存在该字符，则移动到相应的子节点；否则，说明字典树中没有这个字符串。重复这个过程，直到遍历完整个字符串或找到
-
删除字符串：首先查找要删除的字符串，如果找到，则将该字符串对应的节点标记为非结尾。然后从根节点开始，依次遍历每个字符，并检查当前节点的子节点是否只有一个指向其他字符串的路径（即只有一个子节点）。如果是这样，则删除该子节点。重复这个过程，直到遍历完整个字符串或找到没有子节点的节点。最后，如果根节点没有任何子节点，则删除整个字典树。
-
查找前缀：从根节点开始，依次遍历要查找的前缀的每个字符。如果当前节点的子节点中存在该字符，则移动到相应的子节点；否则，说明字典树中没有这个前缀。重复这个过程，直到遍历完整个前缀或找到没有子节点的节点。最后，返回当前节点及其子节点所代表的字符串集合。
字典树的实现
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
| class TrieNode{
public:
unordered_map<char, TrieNode*> children;
bool isEndOfWord;
TrieNode(){
isEndOfWord = false;
}
}
class Trie{
TrieNode* root;
public:
Trie(){
root = new TrieNode();
}
void insert(string word){
TrieNode* node = root;
for(char c : word){
if(!node->children.count(c)){
node->children[c] = new TrieNode();
}
node = node->children[c];
}
node->isEndOfWord = true;
}
bool search(string word){
TrieNode* node = root;
for(char c : word){
if(!node->children.count(c)){
return false;
}
node = node->children[c];
}
return node->isEndOfWord;
}
bool search_pref(string prefix){
TrieNode* node = root;
for(char c : prefix){
if(!node->children.count(c)){
return false;
}
node = node->children[c];
}
return true;
}
void remove(string word){
remove(root, word, 0);
}
void remove(TrieNode* node, string word, int index){
if(index == word.size()){
if(node->isEndOfWord){
node->isEndOfWord = false;
}
return;
}
char c = word[index];
if(node->children.count(c)){
remove(node->children[c], word, index + 1);
if(!node->children[c]->isEndOfWord && node->children[c]->children.empty()){
delete node->children[c];
node->children.erase(c);
}
}
}
}
|
0-1 Trie 字典树 把数字当成2进制字符串
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
| class TrieNode{
public:
vector<TrieNode*> children;
vector<int> counts;
TrieNode(){
children.resize(2, nullptr);
counts.resize(2, 0);
}
}
class Trie{
TrieNode* root;
int max_bit
public:
Trie(){
max_bit = 31;
root = new TrieNode();
}
void insert(int num){
TrieNode* node = root;
for(int i = max_bit; i >= 0; i--){
int bit = (num >> i) & 1;
if(!node->children[bit]){
node->children[bit] = new TrieNode();
}
node->counts[bit]++;
node = node->children[bit];
}
}
void remove(int num){
TrieNode* node = root;
for(int i = max_bit; i >= 0; i--){
int bit = (num >> i) & 1;
node->counts[bit]--;
if(node->counts[bit] == 0){
delete node->children[bit];
node->children[bit] = nullptr;
return;
}
node = node->children[bit];
}
}
int get(int num){
TrieNode* node = root;
int res = 0;
for(int i = max_bit; i >= 0; i--){
int bit = (num >> i) & 1;
int opposite_bit = bit ^ 1;
if(node->children[opposite_bit] && node->counts[opposite_bit]){
res += (1 << i);
node = node->children[opposite_bit];
}else{
node = node->children[bit];
}
}
return res;
}
}
|
字典树的复杂度分析
- 时间复杂度：插入、查找和删除操作的时间复杂度都是O(m)，其中m是要插入或查找的字符串的长度。
- 空间复杂度：字典树的空间复杂度是O(n * m)，其中n是字符串集合的大小，m是字符串的平均长度。
- 字典树可以高效地处理大量字符串的插入、查找和删除操作，尤其适用于需要频繁进行这些操作的场景。
练习用题
- 208. 实现 Trie (前缀树)
- 212. 单词搜索 II
- 421. 数组中两个数的最大异或值
- 745. 前缀和后缀搜索
题解参考：
1、
这个题是字典树的基础应用，把前面代码直接拿来用即可。
2、
先用字典树存储所有单词，然后遍历board，对于每个位置，尝试在当前位置的上下左右四个方向上搜索。
如果查到了结尾，在结果集中加入该单词。
最后返回结果集。
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
| class Solution {
public:
vector<vector<int>> dirs;
Solution(){
dirs ={ {0, 1}, {0, -1}, {1, 0}, {-1, 0}};
}
void dfs(vector<vector<char>>& board, int x, int y, TrieNode* node, string& word, unordered_set<string>& res, vector<vector<bool>>& visited){
if(node->isEndOfWord){
res.insert(word);
if(node->children.empty()){
return;
}
}
for(auto& dir : dirs){
int nx = x + dir[0];
int ny = y + dir[1];
if(nx>=0 && nx<board.size() && ny>=0 && ny<board[0].size() && !visited[nx][ny] && node->children.count(board[nx][ny])){
visited[nx][ny] = true;
word.push_back(board[nx][ny]);
dfs(board, nx, ny, node->children[board[nx][ny]], word, res, visited);
visited[nx][ny] = false;
word.pop_back();
}
}
}
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
vector<vector<bool>> visited;
unordered_set<string> res;
Trie trie;
for(auto& word : words){
trie.insert(word);
}
for(int i = 0; i < board.size(); i++){
for(int j = 0; j < board[0].size(); j++){
if(trie.root->children.count(board[i][j])){
visited[i][j] = true;
string word;
word.push_back(board[i][j]);
dfs(board, i, j, trie.root->children[board[i][j]], word, res, visited);
visited[i][j] = false;
}
}
}
return vector<string>(res.begin(), res.end());
}
}
|
3、
0-1 Trie 字典树 把数字当成2进制字符串
因为是异或，所以只需要找到最大的那个即可。
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
int findMaximumXOR(vector<int>& nums) {
Trie trie;
int res = 0;
for(auto& num : nums){
trie.insert(num);
res = max(res, trie.get(num));
}
return res;
}
}
|
4、
字典树，存储前缀和后缀。用一个做前缀，一个做后缀。
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
| class TrieNode{
unordered_map<char, TrieNode*> children;
vector<int> index;
TrieNode*(){
index=vector<int>();
}
};
class Trieprefix{
TrieNode* root;
public:
Trieprefix(){
root = new TrieNode();
}
void insert(int index, string& word){
TrieNode* node = root;
for(auto& c : word){
if(!node->children.count(c)){
node->children[c] = new TrieNode();
}
node = node->children[c];
node->index.push_back(index);
}
}
vector<int> search(string& word){
TrieNode* node = root;
for(auto& c : word){
if(!node->children.count(c)){
return {};
}
node = node->children[c];
}
return node->index;
}
};
class TrieSuffix{
TrieNode* root;
public:
TrieSuffix(){
root = new TrieNode();
}
void insert(int index, string& word){
TrieNode* node = root;
for(int i = word.size()-1; i >= 0; i--){
if(!node->children.count(word[i])){
node->children[word[i]] = new TrieNode();
}
node = node->children[word[i]];
node->index.push_back(index);
}
}
vector<int> search(string& word){
TrieNode* node = root;
for(int i = word.size()-1; i >= 0; i--){
if(!node->children.count(word[i])){
return {};
}
node = node->children[word[i]];
}
return node->index;
}
};
class WordFilter {
TriePrefix prefix;
TrieSuffix suffix;
int n;
public:
WordFilter(vector<string>& words) {
unordered_map<string, int> index;
for(int i = 0; i < words.size(); i++){
index[words[i]] = i;
}
for(auto& [word, i] : index){
prefix.insert(i, word);
suffix.insert(i, word);
}
n = words.size();
}
int f(string pref, string suff) {
vector<int> prefix_index = prefix.search(pref);
vector<int> suffix_index = suffix.search(suff);
vector<int> hash(n,0);
for(int i: prefix_index){
hash[i] = 1;
}
int ans=-1
for(int i: suffix_index){
if(hash[i]){
ans=fmax(ans,i);
}
}
return ans;
}
};
|
