01.前缀树

• 前缀树又名字典树，单词查找树，Trie树，是一种你那个多路树形结构，是哈希树的变种，效率高，用于快速检索的多叉树结构。
• 用于统计和排序大量字符串，所以经常用做搜索引擎和文本中单词频率统计。
• 优点：最大限度的减少字符串比较，查询效率高。
• 缺点：内存开销大。

如图为前缀树图

最近LC上刷题经常遇到，以下举几个典型题目

02.前缀树算法题

2.1 替换单词

解题思路：

1、由dictionary字符串数组中的字符构建前缀树。

2、如果sentence中的字符串中在前缀树中找到其前缀，那么替换。

3、输出最后替换后的字符串。

struct TrieNode{
    string word;
    TrieNode* next[26];
    TrieNode(){
        memset(next,0,sizeof(next));
        word = "";
    }
};

class Solution {
private:
    TrieNode* root;
public:

    void buildTrie(vector<string>& dicts){
        root = new TrieNode();

        for(const string& dict: dicts){
            TrieNode* cur = root;
            for(const char& c : dict){
                if(cur->next[c - 'a'] == nullptr){
                    cur->next[c - 'a'] = new TrieNode();
                }
                cur = cur->next[c - 'a'];
            }
            cur->word = dict;
        }
    }

    string replaceWords(vector<string>& dictionary, string sentence) {
        buildTrie(dictionary);

        istringstream iss(sentence);
        string tmp;
        string res;
        while(getline(iss, tmp, ' ')){
            TrieNode* cur = root;
            
            for(const char& c : tmp){
                if(cur->next[c - 'a'] == nullptr)
                    break;
                else{
                    cur = cur->next[c - 'a'];
                    if(!cur->word.empty())//说明找到了
                        break;
                }
            }
            res += cur->word.empty() ? tmp : cur->word;
            res += " ";
        }
        res.pop_back();

        return res;
    }
};

2.2 最短的单词编码

解题思路：

1. 当前单词是否属于某个单词的后缀 —> 单词倒序是否属于某个单词的前缀 —> 前缀树
2. 对数组中的字符串我们可以预处理一下 : 根据单词长度进行排序，这样才能逐个判别子串
3. 如果一个单词属于其他字符串的前缀，则不需要加上他的长度，否则 res += (单词长度＋1)

struct Tire {
    Tire* child[26];
    Tire() {
        for (int i = 0; i < 26; ++i){
            child[i] = nullptr;
        }
    }
};

class Solution {
public:
    int minimumLengthEncoding(vector<string>& words) {
        sort(words.begin(),words.end(),[&](string& s1,string& s2){
            return s1.size() > s2.size();
        });
        int res = 0;
        for (int i = 0; i < words.size(); i++) {
            if (isprefix(words[i])) {
                continue;
            } else {
                insert(words[i]);
                res += words[i].size() + 1;
            }
        }
        return res;
    }
private:
    Tire* root = new Tire();

    void insert(string word) {
        Tire* node = root;
        for (int i = word.size() - 1; i >= 0; --i){
            char ch = word[i];
            if (node->child[ch - 'a'] == nullptr) {
                node->child[ch - 'a'] = new Tire();
            }
            node = node->child[ch - 'a'];  
        }
    }

    bool isprefix(string prefix) {
        Tire* node = root;
        for (int i = prefix.size() - 1; i >= 0; --i) {
            char ch = prefix[i];
            if (node->child[ch - 'a'] == nullptr){
                return false;
            }
            node = node->child[ch - 'a'];
        }
        return true;
    }
};

2.3 单词之和

解题思路：

1、用一个哈希map保存已经插入的键值对，如果新插入的与之相同，则直接返回。

2、将新的key插入前缀树，并更新每个前缀的val值，这里的val值是以前缀开头的总和。

3、查询prefix在前缀树里的val值，并返回。

struct Tire{
    Tire* child[26];
    int val;
    Tire() {
        for (int i = 0; i < 26; ++i) {
            child[i] = nullptr;
        }
        val = 0;
    }
};

class MapSum {
public:
    /** Initialize your data structure here. */
    MapSum() {
        root = new Tire();
    }
    
    void insert(string key, int val) {
        //如果存在且相等，直接不用插入
        if(mp.find(key) != mp.end() && mp[key] == val) {
            return;
        }
        //更新到每个字符的值
        int diff = val - mp[key];
        mp[key] = val;

        Tire* cur = root;
        for (int i = 0; i < key.size(); ++i) {
            cur->val += diff;
            if (cur->child[key[i] - 'a'] == nullptr) {
                cur->child[key[i] - 'a'] = new Tire();
            }
            cur = cur->child[key[i] - 'a'];
        }
        cur->val += diff;
    }
    
    int sum(string prefix) {
        Tire* cur = root;
        //遍历到当前字符串最后一个字符获取val值
        for (int i = 0; i < prefix.size(); ++i) {
            cur = cur->child[prefix[i] - 'a'];
            if (cur == nullptr){
                return 0;
            }
        }
        return cur->val;
    }
private:
    Tire* root;
    unordered_map<string,int> mp;
};

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

03.前缀树的应用场景

1. 有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。
2. 1000万字符串，其中有些是重复的，需要把重复的全部去掉，保留没有重复的字符串。请怎么设计和实现？
3. 一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析。
4. 寻找热门查询：搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，这些查询串的重复读比较高，虽然总数是1千万，但是如果去除重复和，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。