前缀树

Trie树（前缀树）

Trie树，又叫字典树、前缀树（Prefix Tree）、单词查找树或键树，是一种多叉树结构。

trie

Trie性质

根节点不包含字符，除根节点外的每一个子节点都包含一个字符
从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串
每个节点的所有子节点包含的字符互不相同

Trie树优缺点

优点

查询和插入的时间效率为O(m), m为查找和插入字符串的长度
不用求Hash值，对短字符串很快

缺点

Trie树的核心思想是空间换时间

代码实现

class TreeNode:
    def __init__(self):
        self.nodes = [None] * 26
        self.count = 0


class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TreeNode()
        self.start_char = ord('a')

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        node = self.root
        for s in word:
            idx = ord(s)-self.start_char
            nxtNode = node.nodes[idx]
            if nxtNode is None:
                nxtNode = TreeNode()
                node.nodes[idx] = nxtNode
            node = nxtNode
        node.count += 1

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """

        node = self.root
        for s in word:
            idx = ord(s)-self.start_char
            nxtNode = node.nodes[idx]
            if nxtNode is None:
                return False
            node = nxtNode

        return node.count > 0

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        node = self.root
        for s in prefix:
            idx = ord(s)-self.start_char
            nxtNode = node.nodes[idx]
            if nxtNode is None:
                return False
            node = nxtNode

        return True