字典树Trie

leetcode 208
Trie(发音为 "try") 是一种树数据结构，可以用于快速查找字符串的前缀，有着广泛的应用，如搜索引擎的自动补全、拼写检查等。
Trie最重要的几个方法有：insert(插入单词以构建Trie), search(查找Trie中是否存在某个单词), startsWith(查找Trie中是否存在某个前缀)。

下面是Trie的实现：

class TrieNode(object):
    """Trie节点."""
    def __init__(self, val):
        """初始化."""
        # 节点值，仅用于打印树，无实际用途
        self.val = val

        # 孩子节点，形式为{char: TrieNode}
        self.childs = dict()

        # 该节点是否是某个单词的结尾，用于单词查找
        self.is_end = False

    def __repr__(self):
        """节点的字符串表示，便于观察Trie构建好后的结构."""
        return 'Node(%s)' % self.val


class Trie:
    def __init__(self):
        """初始化."""
        self.root = TrieNode('')

    def insert(self, word: str) -> None:
        """插入单词."""
        p = self.root
        for c in word:
            if c not in p.childs:
                # 建立该字符对应的子节点
                p.childs[c] = TrieNode(c)

            p = p.childs[c]

        # 记录单词的结尾
        p.is_end = True

    def search(self, word: str) -> bool:
        """查找某个单词是否在Trie中."""
        # 从根节点开始
        p = self.root
        for c in word:  # 往下搜索
            if p.childs and c in p.childs:
                p = p.childs[c]
            else:  # 搜索失败
                return False

        return p.is_end

    def startsWith(self, prefix: str) -> bool:
        """查找某个前缀."""
        p = self.root
        for c in prefix:
            if p.childs and c in p.childs:
                p = p.childs[c]
            else:
                return False

        return True

    def show(self):
        """层序遍历Trie."""
        queue = [self.root]
        while queue:
            q_size = len(queue)
            for i in range(q_size):
                p = queue.pop(0)
                print(p, end=' ')
                for cv in p.childs:
                    queue.append(p.childs[cv])
            print()


if __name__ == '__main__':
    trie = Trie()
    trie.insert('app')
    trie.insert('apple')
    trie.insert('apk')
    trie.insert('home')
    trie.show()

    print(trie.search('app'))
    print(trie.search('appl'))
    print(trie.search('apple'))
    print(trie.startsWith('b'))

输出：

Node() 
Node(a) Node(h) 
Node(p) Node(o) 
Node(p) Node(k) Node(m) 
Node(l) Node(e) 
Node(e) 
True
False
True
False