[LeetCode] 208. 实现 Trie (前缀树)

[Animenzzzz]

题目描述：

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

示例:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // 返回 true
trie.search("app");     // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");   
trie.search("app");     // 返回 true

说明:

你可以假设所有的输入都是由小写字母 a-z 构成的。
保证所有输入均为非空字符串。

解题思路：字典树的一些基本概念和操作的理解。网上扒一些。
Trie树的基本性质：

1. 根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
2. 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
3. 每个节点的所有子节点包含的字符互不相同。
   Trie树的核心思想是空间换时间，利用字符串的公共前缀来减少无谓的字符串比较以达到提高查询效率的目的。

优点

插入和查询的效率很高，都为O(m)，其中 m是待插入/查询的字符串的长度。

1. 关于查询，会有人说 hash 表时间复杂度是O(1)不是更快？但是，哈希搜索的效率通常取决于hash 函数的好坏，若一个坏的 hash 函数导致很多的冲突，效率并不一定比Trie树高。
2. Trie树中不同的关键字不会产生冲突。
3. Trie树只有在允许一个关键字关联多个值的情况下才有类似hash碰撞发生。
4. Trie树不用求 hash 值，对短字符串有更快的速度。通常，求hash值也是需要遍历字符串的。
5. Trie树可以对关键字按字典序排序。

缺点
当 hash 函数很好时，Trie树的查找效率会低于哈希搜索。
空间消耗比较大。

C++解题：

class TrieNode{
public:
    TrieNode *child[26];
    bool isWord;
    TrieNode():isWord(false){
        for (int i = 0; i < 26; i++) child[i] = nullptr;
    }
};

class Trie {
public:
    /** Initialize your data structure here. */
    Trie() {
        root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        TrieNode *p = root;
        for (int i = 0; i < word.size(); i++)
        {
            int val = word[i] - 'a';
            if(!p->child[val]) p->child[val] = new TrieNode();
            p = p->child[val];
        }
        p->isWord = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        TrieNode *p = root;
        for (int i = 0; i < word.size(); i++)
        {
            int val = word[i] - 'a';
            if(!p->child[val]) return false;
            p = p->child[val];
        }
        return p->isWord;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        TrieNode *p = root;
        for (int i = 0; i < prefix.size(); i++)
        {
            int val = prefix[i] - 'a';
            if(!p->child[val]) return false;
            p = p->child[val];
        }
        return true;
    }
private:
    TrieNode *root;
};