字典树及相关问题

字典树模板题

LeetCode 208. 实现Trie（前缀树）

class Trie {
public:
    /** Initialize your data structure here. */
    Trie() {
        isEnd = false;
        fill(begin(next), end(next), nullptr);
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        Trie* curr = this;
        for(auto ch : word){
            if(curr->next[ch-'a'] == nullptr){
                curr->next[ch-'a'] = new Trie();
            }
            curr = curr->next[ch-'a'];
        }
        curr->isEnd = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        Trie* curr = this;
        for(auto ch : word){
            if(curr->next[ch-'a'] == nullptr){
                return false;
            }
            curr = curr->next[ch-'a'];
        }
        return curr->isEnd;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Trie* curr = this;
        for(auto ch : prefix){
            if(curr->next[ch-'a'] == nullptr){
                return false;
            }
            curr = curr->next[ch-'a'];
        }
        return true;
    }
private:
    static const int R = 26;
    Trie* next[R];
    bool isEnd;
};

LeetCode 1032. 字符流
反向建树

class Trie {
public:
    Trie(){
        isEnd = false;
        fill(begin(next), end(next), nullptr);
    }
        
    void insert(const string& word){
        Trie* curr = this;
        for(auto ch=word.rbegin();ch!=word.rend();++ch){
            if(curr->next[*ch-'a'] == nullptr){
                curr->next[*ch-'a'] = new Trie();
            }
            curr = curr->next[*ch-'a'];
        }
        curr->isEnd = true;
    }
        
    bool query(const string& word){
        Trie* curr = this;
        for(auto ch=word.rbegin();ch!=word.rend();++ch){
            if(curr->next[*ch-'a'] != nullptr){
                curr = curr->next[*ch-'a'];
                if(curr->isEnd) return true;
            }else return false;
        }
        return false;
    }
private:     
    static const int R = 26;
    Trie* next[R];
    bool isEnd;
};

class StreamChecker {
public:
    StreamChecker(vector& words) {
        trie = new Trie();
        for(auto& word : words){
            trie->insert(word);
        }
    }
    
    bool query(char letter) {
        buffer.push_back(letter);
        return trie->query(buffer);
    }
private:
    Trie* trie;
    string buffer;
};

/**
 * Your StreamChecker object will be instantiated and called as such:
 * StreamChecker* obj = new StreamChecker(words);
 * bool param_1 = obj->query(letter);
 */

LeetCode 745. 前缀和后缀搜索
对于每个单词，将它所有可能的后缀、分隔符以及单词本身插入到字典树中，同时记录一下这些单词的权重。在查询阶段，可以通过将后缀、分隔符和前缀组合成一个单词进行查询，返回对应的权重即可。例如，对于单词test，我们将test#test，est#test，st#test，t#test以及#test插入到字典树中。在查询时，假如遇到前缀te和后缀t，那么就将它们组合成t#te进行查询。

字典树+DFS

LeetCode 211. 添加与搜索单词

class WordDictionary {
public:
    /** Initialize your data structure here. */
    WordDictionary() {
        isEnd = false;
        fill(begin(next), end(next), nullptr);
    }
    
    /** Adds a word into the data structure. */
    void addWord(string word) {
        WordDictionary* curr = this;
        for(auto ch : word){
            if(curr->next[ch-'a'] == nullptr){
                curr->next[ch-'a'] = new WordDictionary();
            }
            curr = curr->next[ch-'a'];
        }
        curr->isEnd = true;
    }
    
    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    bool search(string word) {
        return search(word.begin(), word.end(), this);
    }
private:
    bool isEnd;
    static const int R = 26;
    WordDictionary* next[R];
    
    template
    bool search(ForwardIt first, ForwardIt last, WordDictionary* root){
        if(first == last) return root->isEnd;
        if(*first == '.'){
            for(int i=0;i < R;++i){
                if(root->next[i] != nullptr && search(first+1, last, root->next[i])) return true;
            }
        }else if(root->next[*first-'a'] != nullptr){
            return search(first+1, last, root->next[*first-'a']);
        }
        return false;
    }
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj->addWord(word);
 * bool param_2 = obj->search(word);
 */

LeetCode 677. 键值映射

class MapSum {
public:
    /** Initialize your data structure here. */
    MapSum() {
        val = 0;
        isEnd = false;
    }
    
    void insert(string key, int val) {
        MapSum* curr = this;
        
        for(auto ch : key){
            if(curr->next.count(ch) == 0){
                curr->next.insert({ch, new MapSum()});
            }
            curr = curr->next[ch];
        }
        curr->val = val;
        curr->isEnd = true;
    }
    
    int sum(string prefix) {
        MapSum* curr = this;
        int ans = 0;
        for(auto ch : prefix){
            if(curr->next.count(ch) == 0){
                return ans;
            }
            curr = curr->next[ch];
        }
        return dfs(curr);
    }
private:
    unordered_map next;
    int val;
    int isEnd;
    
    int dfs(MapSum* root){
        int sum = 0;
        for(auto it : root->next){
            if(it.second != nullptr){
                sum += dfs(it.second);
            }
        }
        if(root->isEnd) sum += root->val;
        return sum;
    }
};

/**
 * Your MapSum object will be instantiated and called as such:
 * MapSum* obj = new MapSum();
 * obj->insert(key,val);
 * int param_2 = obj->sum(prefix);
 */

LeetCode 820. 单词的压缩编码
反向建树+DFS

class Trie {
public:
    Trie() {
        fill(begin(next), end(next), nullptr);
        isEnd = false;
    }
    
    void insert(string words) {
        Trie* curr = this;
        for(auto it = words.crbegin();it != words.crend(); ++it){
            if(curr->next[*it-'a'] == nullptr) {
                curr->next[*it-'a'] = new Trie();
            }
            curr = curr->next[*it-'a'];
        }
        curr->isEnd = true;
    }
    
    int count(Trie* root, int cnt) {
        bool isLeaf = true;
        int sum = 0;
        for(int i = 0;i < R;++i) {
            if(root->next[i] != nullptr) {
                isLeaf = false;
                sum += count(root->next[i], cnt+1);
            }
        }
        return isLeaf ? cnt + 1 : sum;
    }
private:
    static const int R = 26;
    Trie* next[R];
    bool isEnd;
};

class Solution {
public:
    int minimumLengthEncoding(vector& words) {
        Trie* trie = new Trie();
        for(const auto& it : words) {
            trie->insert(it);
        }
        int ans = trie->count(trie, 0);
        return ans ;
    }
};

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