Trie（前缀树）

Trie树是一种用来对大规模字符串组进行处理然后提供查找功能的数据结构，在原理上来说就是一个棵最多有26个孩子（不考虑大小写的话）树，它把每一个添加进来的单词都基于逐个字母进行拆分并放入结构，前缀树有插入，搜索词，搜索前缀的基本功能

• Trie树在Python中最方便的实现方法就是利用字典来实现
• 每插入一个词时，必须在最后末尾加入一个休止符的key来表示曾经插入过这个词而不是只插入过这个前缀而已
• 搜索前缀和搜索词的判断是不一样的
• Trie树有时候是要考虑词搜索词太长击穿Trie树底部的情况（LeetCode有相关题目：Add and Search Word）

下面是leetcode里面直接实现Trie树的一道题，实现了插入，搜索词，搜索前缀的功能：Implement Trie(Prefix Tree)

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: void
        """
        cur = self.root
        for char in word:
            cur = cur.setdefault(char, {})
        cur['#'] = {}


    def search(self, word):
        """
        Returns if the word is in the trie.
        :type word: str
        :rtype: bool
        """
        cur = self.root
        for char in word:
            if char not in cur:
                return False
            cur = cur[char]
        return '#' in cur


    def startsWith(self, prefix):
        """
        Returns if there is any word in the trie that starts with the given prefix.
        :type prefix: str
        :rtype: bool
        """
        cur = self.root
        for char in prefix:
            if char not in cur:
                return False
            cur = cur[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)