Python 字典树的基本原理与实现

2023-04-11 00:00:00 python 字典基本原理

字典树（Trie树）是一种基于字符串的数据结构，用于快速在大量字符串中查找固定前缀或完整字符串。字典树的主要优点是可以在时间复杂度O(m)的情况下查找单词，即使在大量字符串的情况下也不会牺牲效率。

下面是Python中字典树的实现：

class TrieNode:
    def __init__(self):
        self.children = {}
        self.end_of_word = False


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        current = self.root
        for char in word:
            if char not in current.children:
                current.children[char] = TrieNode()
            current = current.children[char]
        current.end_of_word = True

    def search(self, word: str) -> bool:
        current = self.root
        for char in word:
            if char not in current.children:
                return False
            current = current.children[char]
        return current.end_of_word

    def startsWith(self, prefix: str) -> bool:
        current = self.root
        for char in prefix:
            if char not in current.children:
                return False
            current = current.children[char]
        return True

这段代码中，我们首先定义一个Trie节点类，并将insert、search、startsWith三种操作定义在Trie类中。

在TrieNode类中，我们使用字典children存储节点的所有子节点，使用end_of_word表示当前字符是否是单词的结尾。

在insert操作中，我们从根节点开始，扫描单词中的每个字符并逐步向下移动，直到单词的结尾。在移动到每个字符时，如果当前节点的children中没有该字符，则创建一个新的Trie节点并添加到children中。最后，在单词的最后一个字符处标记end_of_word为True。

在search操作中，我们从根节点开始移动，扫描每个字符直到单词结尾。如果在此过程中发现某个字符不在节点的children中，则返回False。否则，我们移动到下一个节点并继续扫描。最后，如果当前节点的end_of_word为True，则表示单词存在。

在startsWith操作中，与search操作类似，我们扫描前缀中的每个字符并向下移动，直到遇到前缀的末尾。如果在此过程中没有找到某个字符，则返回False，否则返回True。

下面是一些演示代码：

# 创建并初始化字典树
trie = Trie()
trie.insert('pidancode.com')
trie.insert('皮蛋编程')
print(trie.search('pidancode.com'))  # True
print(trie.search('PIddancode.com')) # False
print(trie.startsWith('pidan'))      # True
print(trie.startsWith('ping')))      # False

相关文章