回想以前查找英文字典，最常用的方法就是按照单词字符顺序一个字母一个字母对照着查找。

字典树，首先是一个树，其次它能像查英文字典一样查找字符串，它的样子如下图所示：

树中每个非根节点代表一个字符（也可以看作每条边代表一个字符），对于每个粉色的节点，从根节点到该节点的路径表示一个存在的字符串。

初始时，字典树只有一个根节点，表示不存在任何字符串，我们可以通过下面的方法向树中插入字符串：

  1. 节点指针 p 指向字典树根节点，字符 c 表示待插入字符串中第一个字符，走 2;
  2. 若 p 的子节点中存在表示字符 c 的节点，走 3，否则创建一个 p 的子节点，使其表示字符 c，走 3
  3. p 指向 p 的表示字符 c 的子节点，若字符 c 表示待插入字符串中的最后一个字符，走 4，否则字符 c 表示待插入字符串的下一个字符，走 2。
  4. 将 p 所指节点标记为字符串结束节点（即上述粉色节点，可以在节点中设置一个 isEnd 标志），插入结束。

根据下面算法模板看懂插入步骤后，查询单词的步骤也自然明白了，这里不再赘述。

算法模板如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
struct TrieNode // 字符节点
{
    bool isEnd; // 是否为一个单词的结尾
    vector<TrieNode*> children; // 下一个字符节点
    TrieNode() { // 构造函数
        isEnd = false;
        children = vector<TrieNode*>(26, nullptr);
    }
};

// 插入单词 word
void insert(TrieNode* root, const string &word)
{
    auto p = root;
    for(char c : word) // 逐个字符遍历
    {
        int idx = c - 'a';
        if(!p->children[idx]) // 如果这个字符节点还没有，创建节点
            p->children[idx] = new TrieNode();
        p = p->children[idx];
    }
    p->isEnd = true;
}

// 查询单词 word
bool search(TrieNode* root, const string &word)
{
    auto p = root;
    for(char c : word)
    {
        int idx = c - 'a';
        if(!p->children[idx]) // 不存在这个字符
            return false;
        p = p->children[idx];
    }
    return p->isEnd;
}

// 查询是否存在以 prefix 为前缀的单词
bool startsWith(TrieNode* root, const string &prefix) {
    auto p = tree;
    for(char c : prefix)
    {
        int idx = c - 'a';
        if(!p->children[idx])
        	return false;
        p = p->children[idx];
    }
    return true;
}