仰望星空

位我上者，灿烂星空；道德律令，在我心中。

0%

前缀树

发表于 更新于 分类于 ，
本文字数： 6.7k 阅读时长 ≈ 6 分钟

【道德经·第十七章】太上，不知有之。其次，亲而誉之。其次，畏之。其次，侮之。信不足焉，有不信焉。悠兮其贵言。功成事遂，百姓皆谓我自然。

前缀树（Trie）

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

208. 实现 Trie (前缀树)

请你实现 Trie 类。 

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
class TrieNode {
public:
    TrieNode* child[26];
    bool isWord;

    TrieNode() : isWord(false) {
        for(auto& a : child) {
            a = nullptr;
        }
            
    }
    
};

class Trie {
public:
    Trie() {
        root = new TrieNode();
    }
    
    void insert(string word) {
        TrieNode *cur = root;
        for(int i = 0; i < word.size(); i++) {
            int id = word[i]-'a';
            if(cur->child[id] == nullptr) cur->child[id] = new TrieNode();
            cur = cur->child[id]; 
        }
        
        cur->isWord = true;
    }
    
    bool search(string word) {
        TrieNode *cur = root;
        for(int i = 0; i < word.size(); i++) {
            int id = word[i]-'a';
            if(cur->child[id] == nullptr)
                return false;
            
            cur = cur->child[id];
        }
        
        return cur->isWord;
    }
    
    bool startsWith(string prefix) {
        TrieNode *cur = root;
        for(int i = 0; i < prefix.size(); i++) {
            int id = prefix[i]-'a';
            if(cur->child[id] == nullptr)
                return false;
            
            cur = cur->child[id];
        }
        
        return true;
    }
private:
    TrieNode* root;
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

648. 单词替换

给定一个由许多词根组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。你需要将句子中的所有继承词用词根替换掉。 

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 Solution {
public:
    class TrieNode {
    public:
        TrieNode *child[26];
        bool isWord;
        TrieNode() : isWord(false) {
            for(auto& a : child) 
                a = nullptr;
        }
    };
    
    string replaceWords(vector<string>& dictionary, string sentence) {
        string res = "";

        TrieNode *root = new TrieNode();
        for(string& word : dictionary) 
            insert(root, word);
        
        istringstream in(sentence);
        string t = "";
        while(in >> t) {
            if(!res.empty()) res += " ";
            res += findPrefix(root, t);
        }
         
        return res;
    }
    
    void insert(TrieNode* root, string& word) {
        TrieNode *cur = root;
        for(int i = 0; i < word.size(); i++) {
            int id = word[i]-'a';
            if(cur->child[id] == nullptr) cur->child[id] = new TrieNode();
            
            cur = cur->child[id];
        }
        
        cur->isWord = true;
    }
    
    string findPrefix(TrieNode* node, string& word) {
        string cur = "";
        for(char c : word) {
            if(node->child[c-'a'] == nullptr)
                break;
            
            cur.push_back(c);
            node = node->child[c-'a'];
            if(node->isWord) return cur;
        }
        
        return word;
        
    }
    
private:
    TrieNode *root;  
};

676. 实现一个魔法字典

设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。
如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。

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
class MagicDictionary {
public:
    class TrieNode {
    public:
        TrieNode *child[26];
        bool isWord;
        TrieNode() : isWord(false) {
            for(auto& a : child) 
                a = nullptr;
        }
    };

    TrieNode *root;
    MagicDictionary() {
        root = new TrieNode();
    }
    
    void buildDict(vector<string> dictionary) {
        for(int i = 0; i < dictionary.size(); i++) {
            insert(root, dictionary[i]);
        }
    }
    
    bool search(string searchWord) {
        return dfs(root, searchWord, 0, 0);
    }
    
    bool dfs(TrieNode* root, string& word, int i, int edit) {
        if(root == nullptr) return false;
        
        if(root->isWord==true && i==word.size() && edit==1) 
            return true;
        
        if(i<word.size() && edit<=1){
            bool found = false;
            for(int j = 0; j<26 && !found; j++) {
                int newEdit = (word[i]-'a' == j) ? edit : edit+1;
                found = dfs(root->child[j], word, i+1, newEdit);
            }
            
            return found;
        }
        
        return false;
    }
    
    void insert(TrieNode* root, string& word) {
        TrieNode *cur = root;
        for(int i = 0; i < word.size(); i++) {
            int id = word[i]-'a';
            if(cur->child[id] == nullptr) {
                cur->child[id] = new TrieNode();
            }
            cur = cur->child[id];
        }
        
        cur->isWord = true;
    }
};

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * MagicDictionary* obj = new MagicDictionary();
 * obj->buildDict(dictionary);
 * bool param_2 = obj->search(searchWord);
 */

820. 单词的压缩编码

给你一个单词数组 words ，返回成功对 words 进行编码的最小助记字符串 s 的长度 。

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
class Solution {
public:
    struct TrieNode {
        TrieNode *child[26];
        TrieNode() {
            for(int i = 0; i < 26; i++) {
                child[i] = nullptr;
            }
        }
    };
    
    void dfs(TrieNode* node, int& ans, int dep) {
        bool isLeaf = true;
        for(int i = 0; i < 26; i++) {
            if(node->child[i]) {
                isLeaf = false;
                dfs(node->child[i], ans, dep+1);
            }
        }
        
        if(isLeaf) ans += dep;
    }
    
    int minimumLengthEncoding(vector<string>& words) {
        root = new TrieNode();
        for(string& s : words) {
            TrieNode *node = root;
            for(int i = s.size()-1; i >= 0; i--) {
                int id = s[i]-'a';
                if(!node->child[id]) node->child[id] = new TrieNode();
                node = node->child[id];
            }
        }
        
        int ans = 0;
        dfs(root, ans, 1);
        return ans;
    }
    
private:
    TrieNode *root;
};

677. 键值映射

设计一个 map ，满足以下几点: 字符串表示键，整数表示值；返回具有前缀等于给定字符串的键的值的总和

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
class MapSum {
public:
    struct TrieNode {
        int val;
        TrieNode *child[26];
        TrieNode() : val(0){
            for(int i = 0; i < 26; i++) {
                child[i] = nullptr;
            }
        }
    };
    
    MapSum() {
        root = new TrieNode();
    }
    
    void insert(string key, int val) {
        TrieNode *cur =  root;
        for(int i = 0; i < key.size(); i++) {
            int id = key[i]-'a';
            if(cur->child[id] == nullptr) cur->child[id] = new TrieNode();
            cur = cur->child[id];
        }
        
        cur->val = val;
    }
    
    int sum(string prefix) {
        TrieNode *cur = root;
        for(int i = 0; i < prefix.size(); i++) {
            int id = prefix[i]-'a';
            if(cur->child[id] == nullptr) return 0;
            cur = cur->child[id];
        }
        
        return getSum(cur);
    }
    
    int getSum(TrieNode* node) {
        if(!node) return 0;
        
        int ans = node->val;
        for(int i = 0; i < 26; i++) {
            ans += getSum(node->child[i]);
        }
        
        return ans;
    }
    
private:
    TrieNode *root;
};

421. 数组中两个数的最大异或值

给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。

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
class Solution {
public:
    struct TrieNode {
        TrieNode *child[2];
        TrieNode() {
            for(int i = 0; i < 2; i++) {
                child[i] = nullptr;
            }
        }
    };
    
    int findMaximumXOR(vector<int>& nums) {
        root = new TrieNode();
        for(int num : nums) {
            TrieNode *node = root;
            for(int i = 31; i >= 0; i--) {
                int bit = (num>>i)&1;
                if(!node->child[bit]) node->child[bit] = new TrieNode();
                node = node->child[bit];
            }
        }
        
        int ans = 0;
        for(int num : nums) {
            TrieNode *node = root;
            int t = 0;
            for(int i = 31; i >= 0; i--) {
                int bit = (num>>i)&1;
                if(node->child[1-bit]) {
                    t = (t<<1) + 1;
                    node = node->child[1-bit];
                } else {
                    t = t<<1;
                    node = node->child[bit];
                }
            }
            
            ans = max(ans, t);
        }
        
        return ans;
    }
      
private:
    TrieNode *root;
};

位我上者，灿烂星空；道德律令，在我心中。