前缀树

前缀树（又称为字典树或者称为字典映射树、查找树），是一种树形结构。前缀树的作用是：对于一组字符串，找到这组字符串的公共前缀，或者判断一个字符串是否是这组字符串中的某一个串的前缀。

前缀树的主要性质是：根节点不包含字符,每一个节点的所有子节点包含的字符都不相同。另外，从根节点到某一个节点，路径上经过的字符连接起来，即为该节点对应的字符串。

以下是前缀树的时间复杂度描述：

空间复杂度	时间复杂度	空间复杂度描述	时间复杂度描述
O(字符串总长度)	O(字符串总长度)	各字符串的字符数之和	查找、插入、删除的时间复杂度均为O(字符串长度)

字典树的应用场景非常广泛，比如字符串的匹配 (Trie), 排序、树形统计和信息检索 (eg. 索引, 关键词检索, 模糊查询) 等等。

前缀树的实现代码如下：

class Trie 
{
public:
    vector<Trie*> children;
    bool is_end_;
    Trie() : children(26),  is_end_(false)
    {   
    }
    
    void insert(string word)    // 输入字符串
    {
        Trie *node = this;
        for(auto &c : word)
        {
            if(node -> children[c - 'a'] == nullptr)
                node -> children[c - 'a'] = new Trie();

            node = node -> children[c - 'a'];
        }
        node -> is_end_ = true;

    }

    bool search(string word)    // 查找word是否在前缀树中插入过
    {
        Trie *node = searchPrefix(word);
        return node != nullptr && node -> is_end_ == true;
    }
    
    bool startsWith(string prefix)  // 判断是否以word为前缀
    {
        return searchPrefix(prefix);
    }

    Trie* searchPrefix(string word) 
    {
        Trie *node = this;
        for(auto &c : word)
        {
            if(node -> children[c - 'a'] == nullptr)
                return nullptr;
            node = node -> children[c - 'a'];
        }
        return node;
    }
};