trie python

Trie，也叫字典树或前缀树，是一种树形数据结构，用于高效地存储和检索字符串数据集中的键值。在Trie中，每个节点代表一个字符串（或键值），从根节点到叶子节点的路径表示该字符串。Trie的一个重要应用是前缀匹配，可以用于实现自动补全、拼写检查等功能。

在Python中，可以使用字典来实现Trie。具体来说，每个节点是一个字典，键是字符，值是下一个节点的字典。根节点是一个空字典。以下是一个简单的Trie实现：

class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node:
                node[c] = {}
            node = node[c]
        node['$'] = None

    def search(self, word):
        node = self.root
        for c in word:
            if c not in node:
                return False
            node = node[c]
        return '$' in node

    def startsWith(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node:
                return False
            node = node[c]
        return True

这个实现支持插入、查找和前缀匹配操作。插入操作将一个字符串插入到Trie中，查找操作判断一个字符串是否在Trie中，前缀匹配操作判断是否存在以某个前缀开头的字符串。