题目：实现一个 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树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。”
因为限定都是由a-z小写字母构成，所以这棵树是一棵26叉树。前缀树的构造过程，通过不断插入新的字符串来丰富这棵26叉树。前缀树的功能很强大，可以做文本词频统计，例如我们在搜索框中的搜索提示，就可以利用前缀树实现。因此，前缀树基本的操作是字符串的插入insert，搜索search，删除delete，查找前缀startsWith等。
思路：
一个Trie是通过不断insert新的字符串不断变大的。那么我们关注insert操作如何实现，便知道Trie的构造。以上面的例子为例，在构造完一个根节点后，我们要插入“apple”这个单词。我们要循着“a->p->p->l->e这个路径去逐个确认每一个前缀是否已经存在，如果不存在，就建立出这个前缀的最后一个根节点，如果存在，就继续确认下一个字母”。
解法1#：用dict模拟字典树
class Trie(object): def __init__(self): """ Initialize your data structure here. """ self.root = {} def insert(self, word): """ Inserts a word into the trie. :type word: str :rtype: None """ node = self.root for char in word: node = node.setdefault(char, {}) node["end"] = True def search(self, word): """ Returns if the word is in the trie. :type word: str :rtype: bool """ node = self.root for char in word: if char not in node: return False node = node[char] return "end" in node def startsWith(self, prefix): """ Returns if there is any word in the trie that starts with the given prefix. :type prefix: str :rtype: bool """ node = self.root for char in prefix: if char not in node: return False node = node[char] return True # Your Trie object will be instantiated and called as such: # obj = Trie() # obj.insert(word) # param_2 = obj.search(word) # param_3 = obj.startsWith(prefix)解法2#：通过创建树节点形式实现
class TrieNode(object): # Initialize your data structure here. def __init__(self): self.children = collections.defaultdict(TrieNode) self.is_word = False class Trie(object): def __init__(self): """ Initialize your data structure here. """ self.root = TrieNode() def insert(self, word): """ Inserts a word into the trie. :type word: str :rtype: void """ node = self.root for chars in word: child = node.data.get(chars) if not child : node.data[chars] = TrieNode() node = node.data[chars] node.is_word = True def search(self, word): """ Returns if the word is in the trie. :type word: str :rtype: bool """ node = self.root for chars in word: node = node.data.get(chars) if not node: return False # 判断单词是否是完整的存在在trie树中 return node.is_word def startsWith(self, prefix): """ Returns if there is any word in the trie that starts with the given prefix. :type prefix: str :rtype: bool """ node = self.root for chars in prefix: node = node.data.get(chars) if not node: return False return True # Your Trie object will be instantiated and called as such: # obj = Trie() # obj.insert(word) # param_2 = obj.search(word) # param_3 = obj.startsWith(prefix)
参考：
https://blog.csdn.net/IOT_victor/article/details/88936762
https://blog.csdn.net/qq_32424059/article/details/89005563
https://blog.csdn.net/ANNILingMo/article/details/80879910
https://blog.csdn.net/qq_33297776/article/details/82315859
