题目链接：Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.

Note:

You may assume that all inputs are consist of lowercase letters a-z.

这道题的要求是实现字典树（Trie）的insert、search、startsWith操作，其中所有输入只包含小写字母a~z。

Trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。

典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。

字典树有一些特性：

  1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符；
  2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
  3. 每个节点的所有子节点包含的字符都不相同。

例如and、as、at、cn、com这些关键词将被表示成：

      root
     /    \
    a      c
   /|\    / \
  n s t  n   o
 /            \
d              m

字典树插入的方法为：

  1. 从根结点开始一次搜索；
  2. 取得要插入关键词的第一个字母，并根据该字母选择对应的子树，如果该子树为空，这新建节点作为该子树。接下来转到该子树继续进行检索；
  3. 在相应的子树上，取得要插入关键词的第二个字母，并进一步选择对应的子树进行检索；
  4. 重复2和3的迭代过程……
  5. 在某个结点处，关键词的所有字母均读取完成，则完成插入。

字典树搜索的方法为：

  1. 从根结点开始一次搜索；
  2. 取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索；
  3. 在相应的子树上，取得要查找关键词的第二个字母，并进一步选择对应的子树进行检索。
  4. 重复2和3的迭代过程……
  5. 在某个结点处，关键词的所有字母已被取出，则完成查找；或者到达叶子节点后关键词字符并没有查找完，则说明没有找到。

而对应此题，需要由于需要搜索单词，因此需要在每个节点中用bool类型遍历is_word表示到达该节点时是否构成单词。

时间复杂度：O(l)（l为字符串长度）

空间复杂度：O(26^n)

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
51
52
53
54
55
56
57
58
59

class TrieNode
{
public:
    TrieNode *next[26];
    bool is_word;
    
    // Initialize your data structure here.
    TrieNode(bool b = false)
    {
        memset(next, 0, sizeof(next));
        is_word = b;
    }
};

class Trie
{
    TrieNode *root;
public:
    Trie()
    {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    void insert(string s)
    {
        TrieNode *p = root;
        for(int i = 0; i < s.size(); ++ i)
        {
            if(p -> next[s[i] - 'a'] == NULL)
                p -> next[s[i] - 'a'] = new TrieNode();
            p = p -> next[s[i] - 'a'];
        }
        p -> is_word = true;
    }

    // Returns if the word is in the trie.
    bool search(string key)
    {
        TrieNode *p = find(key);
        return p != NULL && p -> is_word;
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    bool startsWith(string prefix)
    {
        return find(prefix) != NULL;
    }

private:
    TrieNode* find(string key)
    {
        TrieNode *p = root;
        for(int i = 0; i < key.size() && p != NULL; ++ i)
            p = p -> next[key[i] - 'a'];
        return p;
    }
};