Trie[字典树]详细总结及例题[给定题解AC beats>=90%]

1. Trie树

Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。

Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

它有3个基本性质：

1.根节点不包含字符，除根节点外每一个节点都只包含一个字符。

2.从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。

3.每个节点的所有子节点包含的字符都不相同。

2.字典树的构建

题目：给你100000个长度不超过10的单词。对于每一个单词，我们要判断他出没出现过，如果出现了，求第一次出现在第几个位置。

分析：这题当然可以用hash来解决，但是本文重点介绍的是trie树，因为在某些方面它的用途更大。比如说对于某一个单词，我们要询问它的前缀是否出现过。这样hash就不好搞了，而用trie还是很简单。

假设我要查询的单词是abcd，那么在他前面的单词中，以b，c，d，f之类开头的我显然不必考虑。而只要找以a开头的中是否存在abcd就可以了。同样的，在以a开头中的单词中，我们只要考虑以b作为第二个字母的，一次次缩小范围和提高针对性，这样一个树的模型就渐渐清晰了。

好比假设有b，abc，abd，bcd，abcd，efg，hii 这7个单词，我们构建的树就是如下图这样的：

对于每一个节点，从根遍历到他的过程就是一个单词，如果这个节点被标记为红色，就表示这个单词存在，否则不存在。

3.模版

几个基本的操作：

1.初始化以及插入

2.查找

3.删除

4.替换

5.累加得值（再加上一个dfs即可）

4.下面几道典型的应用

208. Implement Trie (Prefix Tree)

很典型的，实现上面说的1,2操作，做完这题把它当成一个模板即可。

struct TrieNode{
    bool flag;
    TrieNode* children[26];
    TrieNode(){
        flag=false;
        for(int i=0;i<26;++i)
            children[i]=NULL;
    }
};
class Trie {
public:
    /** Initialize your data structure here. */
    Trie() {
        root=new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        TrieNode* p=root;
        for(auto cur:word){
            int val=cur-'a';
            if(p->children[val]==NULL)
                p->children[val]=new TrieNode();
            p=p->children[val];
        }
        p->flag=true; //current status is true
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        TrieNode* p=root;
        for(auto cur:word){
            int val=cur-'a';
            if(p->children[val]==NULL)
                return false;
            p=p->children[val];
        }
        return p->flag; //don't return true directly
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        TrieNode* p=root;
        int idx;
        for(idx=0;idx<prefix.length();++idx){
            int val=prefix[idx]-'a';
            if(p->children[val]==NULL)
                return false;
            p=p->children[val];
        }
        return true;
    }
private:
    TrieNode* root;
};

 leetcode 472. Concatenated Words

这时候，给定的单词表中，至少由两个短的单词组成的，可以算作一个concatenated word，返回总的个数。那么就是我提到的第5点，在分割单词的时候使用dfs即可。

struct TrieNode{
    bool flag;
    TrieNode* child[26];
    TrieNode(){
        flag=false;
        for(int i=0;i<26;++i)
            child[i]=NULL;
    }
};
class Solution {
public:
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        vector<string> res;
        root=new TrieNode();
        auto cmp=[](const string&a,const string&b){
            return a.length()<b.length();
        };
        sort(words.begin(),words.end(),cmp); //sort by the length, so we won't miss the answer
        for(int i=0;i<words.size();++i){
            string word=words[i];
            if(dfs(word))
                res.push_back(word);
            insert(word);
        }
        return res;
    }
private:
    TrieNode* root;
    
    bool search(string word){ //search in the Trie
        TrieNode* p=root;
        for(int i=0;i<word.length();++i){
            int val=word[i]-'a';
            if(p->child[val]==NULL)
                return false;
            p=p->child[val];
        }
        return p->flag;
    }
    
    void insert(string word){ //build the Trie
        TrieNode* p=root;
        for(int i=0;i<word.length();++i){
            int val=word[i]-'a';
            if(p->child[val]==NULL)
                p->child[val]=new TrieNode();
            p=p->child[val];
        }
        p->flag=true;
    }
    
    bool dfs(string word){ //dfs to split the word and check
        string str="";
        for(int i=0;i<word.length();++i){
            str+=word[i];
            string after=word.substr(i+1); //split the word to two parts
            if(search(str) && after!=""){
                if(search(after) || dfs(after))
                    return true;
            }
        }
        return false;
    }
};

leetcode 648 Replace Words

注意不要死板，search或者查找整个单词返回值可以不止是flag嘛！

像这道题，我给定一系列的word，如果存在有最短前缀，那么我将word进行前缀替换。此时想到，既然要找寻这个最小的前缀，那么我何不直接返回这个前缀的整个长度呢？那想到这点之后，剩下的下面的解法都没什么好说的了，直接按照模板来即可。

struct TrieNode{
    bool flag;
    TrieNode* children[26];
    TrieNode(){
        flag=false;
        for(int i=0;i<26;++i)
            children[i]=NULL;
    }
};
class Trie{
public: 
    Trie(){
        root=new TrieNode();
    }
    
    void insert(string word){
        TrieNode* p=root;
        for(int i=0;i<word.length();++i){
            int val=word[i]-'a';
            if(p->children[val]==NULL)
                p->children[val]=new TrieNode();
            p=p->children[val];
        }
        p->flag=true;
    }
    
    int search(string word){ //this time to check the prefix of the word,not the word itself and return the index(length)
        TrieNode* p=root;
        int idx;
        for(idx=0;idx<word.length();++idx){
            int val=word[idx]-'a';
            if(p->children[val]==NULL)
                break;
            p=p->children[val];
            if(p->flag)
                return idx+1; //already find the prefix in the given vector
        }
        return 0; //cant find the prefix
    }
private:
    TrieNode* root;
};

class Solution {
public:
    string replaceWords(vector<string>& dict, string sentence) {
        Trie sol; //to creat a Trie object
        //insert all the words in the dict
        for(auto word:dict)
            sol.insert(word);
        // dfs to search the word
        string s;
        string res;
        istringstream in(sentence);
        while(in>>s){
            int len=sol.search(s);
            if(len==0)
                res+=s+" ";
            else
                res+=s.substr(0,len)+" ";
        }
        if(!res.empty()) //to pop back the last " "
            res.pop_back();
        return res;
    }
};