LC208：Trie前缀树

算是对 Acwing 那题的复习了

题目如下：

思路就不说了，就是将字符串按照多叉树存储，插入和查询差不多，只要把每个字符串结尾的字符标记一下或者记录一下个数就行。

下面是代码：

class Trie {

public:

    static const int N = 100010;
    int son[N][26] = {0};  //son[1][2] = 3; 说明节点1有一个节点3的儿子字符C（0-25）
    int cnt[N] = {0}; //存以当前节点为结尾的字符串有多少个
    int idx = 0;  //存节点序号

    Trie() {
    }

    void insert(string word) {

        int p = 0;  //0是所有节点的根节点
        int size = word.size();
        for(int i = 0; i < size; i++){
            int u = word[i] - 'a';
            if(!son[p][u]) son[p][u] = ++idx;  //没有值为这个字符的子节点就创建并编号
            p = son[p][u];  //并且就移动到孩子节点,进行下一个字符的插入
        }
        cnt[p]++;
    }
    bool search(string word) {
        int p = 0;
        int size = word.size();
        for(int i = 0; i < size; i++){
            int u = word[i]-'a';
            if(!son[p][u]) return false; //字符断了，说明没有这个前缀单词
            p = son[p][u];  //移动到孩子
        }
        return cnt[p] > 0;  //以当前字符串结尾的单词存在，说明word存在
    }

    //自定义查询前缀
    bool startsWith(string prefix) {
        int p = 0;
        int size = prefix.size();
        for(int i = 0; i < size; i++){
            int u = prefix[i]-'a';
            if(!son[p][u]) return false; //字符断了，说明没有这个前缀单词
            p = son[p][u];  //移动到孩子
        }
        return true;  //到达了当前字符串的尾部，说明存在
    }
};