字典树trie

字典树Trie又称为前缀树PrefixTree，主要用于高效解决前缀相关的问题。常见的Trie有数字Trie，字母Trie，以及01-Trie。

这里以字母Trie为例介绍其用法，要求实现添加单词，查找单词和查找前缀的功能，详情可参考这里。

首先需要定义树节点结构。

struct Node {
    int val;
    struct Node *next[26];
}root;

插入由小写字母构成的单词。

void insert(string &word) {
    Node *p = &root;
    for (auto i : word) {
        int d = i - 'a';
        if (p->next[d] == NULL)
            p->next[d] = new Node();
        p = p->next[d];
    }
    p->val += 1;
}

给定由小写字母构成的单词，问集合中是否存在。

bool search(string &word) {
    Node *p = &root;
    for (auto i : word) {
        int d = i - 'a';
        if (p->next[d] == NULL)
            return false;
        p = p->next[d];
    }
    return p->val > 0;
}

给定由小写字母构成的串，问集合中是否存在以该串为前缀的单词。

bool startsWith(string &prefix) {
    Node *p = &root;
    for (auto i : prefix) {
        int d = i - 'a';
        if (p->next[d] == NULL)
            return false;
        p = p->next[d];
    }
    return true;
}