字典树的基础算法

字典树

字典树是一种树形结构，用于存储字符串集合。它的每个节点代表一个字符，从根节点到某个节点的路径代表一个字符串。字典树可以高效地插入、删除和查找字符串。

字典树的基本操作

  1. 插入字符串：从根节点开始，依次遍历字符串的每个字符，如果当前节点不存在该字符的子节点，则创建一个新的子节点，并将当前节点指向该子节点。重复这个过程，直到遍历完整个字符串。最后，将当前节点标记为字符串的结尾。

  2. 查找字符串：从根节点开始，依次遍历要查找的字符串的每个字符。如果当前节点的子节点中存在该字符，则移动到相应的子节点；否则，说明字典树中没有这个字符串。重复这个过程，直到遍历完整个字符串或找到

  3. 删除字符串：首先查找要删除的字符串，如果找到，则将该字符串对应的节点标记为非结尾。然后从根节点开始，依次遍历每个字符，并检查当前节点的子节点是否只有一个指向其他字符串的路径（即只有一个子节点）。如果是这样，则删除该子节点。重复这个过程，直到遍历完整个字符串或找到没有子节点的节点。最后，如果根节点没有任何子节点，则删除整个字典树。

  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{
public:
    // 存储子节点的哈希表
    unordered_map<char, TrieNode*> children;
    // 标记是否为单词结尾
    bool isEndOfWord;
    // 构造函数，初始化isEndOfWord为false
    TrieNode(){
        isEndOfWord = false;
    }
}

class Trie{
    // 根节点
    TrieNode* root;
public:
    // 构造函数，初始化根节点
    Trie(){
        root = new TrieNode();
    }

    // 插入单词
    void insert(string word){
        TrieNode* node = root;
        // 遍历单词的每个字符
        for(char c : word){
            // 如果当前字符不在子节点中，则创建一个新的TrieNode
            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){
            // 如果当前字符不在子节点中，则返回false
            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){
            // 如果当前字符不在子节点中，则返回false
            if(!node->children.count(c)){
                return false;
            }
            // 移动到子节点
            node = node->children[c];
        }
        // 返回true
        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;
    }
}

字典树的复杂度分析

  1. 时间复杂度：插入、查找和删除操作的时间复杂度都是O(m)，其中m是要插入或查找的字符串的长度。
  2. 空间复杂度：字典树的空间复杂度是O(n * m)，其中n是字符串集合的大小，m是字符串的平均长度。
  3. 字典树可以高效地处理大量字符串的插入、查找和删除操作，尤其适用于需要频繁进行这些操作的场景。

练习用题

  1. 208. 实现 Trie (前缀树)
  2. 212. 单词搜索 II
  3. 421. 数组中两个数的最大异或值
  4. 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;
    }
};