LeetCode 208 Implement Trie (Prefix Tree)（实现前缀树）（*）

翻译

实现一个包含insert，search和startsWith方法的前缀树。

备注：
你可以假定所有的输入只包含小写字母a-z。

原文

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

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

分析

其实一开始我也不懂什么是前缀树（这个单词我都不认识……

所以只能去看官网给的解释了，所以下面的内容是翻译。

Trie （我们读作“try”）或prefix tree是一种树形数据结构，它被用作检索字符串数据集的密钥。这有关于这个高效的数据结构的不同应用：

1 . 自动补全

2 . 拼写检查

3 . IP路由

4 . T9文字输入法

5 . 解决单词游戏

这里有很多别的数据结构，比如说平衡树和哈希表，它们都可以给我们在字符串数据集中搜索一个单词的可能。那我们为什么还需要前缀树呢？尽管哈希表对查找一个key的时间复杂度是$O(n)$，但是它对于下面的操作并不高效：

• 找出一个公共前缀的所有键
• 以字典序枚举字符串数据集

另一个前缀树性能优于哈希表的原因是当哈希表在大小上猛烈增长时，在哈希表上会存在很多哈希冲突并且搜索时间复杂度也会恶化到$O(n)$，其中$n$是被插入的键的数量。和哈希表相比，当存储相同前缀的很多键时，前缀树只需要更少的空间。当m为键的长度时，前缀树只需要$O(m)$的时间复杂度。另外在平衡树中搜索一个键的时间复杂度是$O(mlogn)$。

前缀树节点结构

前缀树是一个根树，它的节点包含以下领域：

• 最大值R对应于它的子节点们，每个链路对应于来自英语字母表数据集R字符值之一。在这篇文章中，我们假定R是26，也就是小写拉丁字母的数量。
• 布尔变量，表示该节点是否对应于一个key的尾部，或仅仅是这个key前缀本身。

Java代码如下：

class TrieNode {

    // R links to node children
    private TrieNode[] links;

    private final int R = 26;

    private boolean isEnd;

    public TrieNode() {
        links = new TrieNode[R];
    }

    public boolean containsKey(char ch) {
        return links[ch -'a'] != null;
    }
    public TrieNode get(char ch) {
        return links[ch -'a'];
    }
    public void put(char ch, TrieNode node) {
        links[ch -'a'] = node;
    }
    public void setEnd() {
        isEnd = true;
    }
    public boolean isEnd() {
        return isEnd;
    }
}

在前缀树中最常用的两个公共操作是插入和搜索key。

插入key到前缀树

我们通过搜索来插入一个键到前缀树中。从根部开始搜索一个链表，其对应于首个键字母。这里有两个例子：

• 该链表存在。那么我们就接着往下走，到下一个子节点。算法会继续搜索下一个key字母。
• 链表不存在。那么我们就要创建一个新的节点，并将其连接到父节点且要和当前的字母匹配。重复这个步骤直到计数到最后一个key，然后标记这个当前节点为尾节点，算法结束。

Java代码如下：

class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    public void insert(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char currentChar = word.charAt(i);
            if (!node.containsKey(currentChar)) {
                node.put(currentChar, new TrieNode());
            }
            node = node.get(currentChar);
        }
        node.setEnd();
    }
}

复杂度分析：
时间复杂度：$O(m)$，其中m是key的长度。
在算法的每个迭代中，要么检索到该节点，要么创建一个新节点，直到遍历到key的尾部。所以它需要m次操作。

空间复杂度：$O(m)$。
最坏的情况是新插入的key并没有已经存在于前缀树中。我们不得不添加m个新节点，所以需要$O(m)$的空间。

在前缀树中搜索key

前缀树中的每个key代表了从根节点到某个内部节点或叶节点的路径。我们从作为首个key字母的根节点开始。检索对应于该键的字符链表的每个当前结点。这有两种情况：

• 链表存在。我们根据这个链表移动到下一个节点，而且继续去搜索下一个key字符。
• 链表不存在。如果已经没有可以搜索的key字符，或当前节点被标记为isEnd，我们就返回true。否则对于这两种可能的情况我们返回false：
  
  • 这有key字符遗留，但它并不和前缀树中的key路径匹配。
  • 没有key字符遗留，但是当前的节点没被标记为isEnd。因此这个搜索的key是该前缀树的另一个key的前缀。

Java代码如下：

class Trie {
    ...

    // search a prefix or whole key in trie and
    // returns the node where search ends
    private TrieNode searchPrefix(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
           char curLetter = word.charAt(i);
           if (node.containsKey(curLetter)) {
               node = node.get(curLetter);
           } else {
               return null;
           }
        }
        return node;
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
       TrieNode node = searchPrefix(word);
       return node != null && node.isEnd();
    }
}

复杂度分析：
时间复杂度：$O(m)$，算法的每一步，我们都要搜索下一个key字母。最坏的情况下需要执行m次操作。
空间复杂度：$O(1)$。

在前缀树中搜索key前缀

这个实现和用于在前缀树中搜索key非常类似。我们从根部开始遍历，直到key前缀中不存在字符遗留，或它不可能继续根据当前的key字符走下去。这前面提到的searchPrefix方法唯一的不同是，当我们走到key前缀的尾部时，我们总是返回true。我们不必去考虑当前前缀树节点是否被标记为isEnd，因为我们搜索的是key的前缀，而不是整个key。

Java代码如下：

class Trie {
    ...

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        TrieNode node = searchPrefix(prefix);
        return node != null;
    }
}

复杂度分析：
时间复杂度：$O(m)$。
空间复杂度：$O(1)$。

代码

Ok，下面是改写的C++代码……有问题请指出。

class TrieNode {
private:
    TrieNode *links[26];
    bool isEnd;
public:
    TrieNode() {
        memset(links, 0, sizeof(links));
    }
    bool containsKey(char c) {
        return links[c - 'a'] != NULL;
    }
    TrieNode* get(char c) {
        return links[c - 'a'];
    }
    void put(char c, TrieNode *node) {
        links[c - 'a'] = node;
    }
    void setEnd() {
        isEnd = true;
    }
    bool getEnd() {
        return isEnd;
    }
};

class Trie {
private:
    TrieNode *root;
    // Returns if the word is in the trie.
    TrieNode* searchPrefix(string word) {
        TrieNode *node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word[i];
            if (node->containsKey(c)) {
                node = node->get(c);
            } else {
                return NULL;
            }
        }
        return node;
    }
public:
    Trie() {
        root = new TrieNode();
    }
    // Inserts a word into the trie.
    void insert(string word) {
        TrieNode *node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word[i];
            if (!node->containsKey(c)) {
                node->put(c, new TrieNode());
            }
            node = node->get(c);
        }
        node->setEnd();
    }
    bool search(string word) {
       TrieNode *node = searchPrefix(word);
       return node != NULL && node->getEnd();
    }
    // Returns if there is any word in the trie
    // that starts with the given prefix.
    bool startsWith(string prefix) {
        TrieNode *node = searchPrefix(prefix);
        return node != NULL;
    }
};