python 字典树算法详解

2023-02-23 00:00:00 算法 字典 详解

字典树（Trie 树）是一种数据结构，用于高效地存储和检索字符串集合。它的基本思想是用树形结构来存储一组字符串，其中每个节点代表一个字符串的前缀，从根节点到叶子节点的路径表示一个字符串。每个节点包含一个字符和一个指向下一个节点的指针。

字典树的核心思想是前缀共享，即多个字符串的前缀可以共用一个节点。例如，假设有以下字符串集合：

["apple", "application", "banana", "band"]

它们可以被组织成如下的字典树：

         root
       /   |   \
      a    b    #
     / \    \
    p   #    a
   / \       |
  p   l      n
 /     \    / \
l       e  d   #
         |  |
         i  a
         |  |
         o  n
         |  |
         n  d

在字典树中，每个节点代表一个字符，从根节点到叶子节点的路径表示一个字符串。节点上的 # 表示该节点是一个字符串的结尾。

实现一个字典树需要定义一个 TrieNode 类来表示每个节点，包含一个字符、一个布尔值表示是否是一个字符串的结尾，以及一个指向下一个节点的字典（Python 中的实现是一个字典）。

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

然后定义 Trie 类来管理字典树，包含一个根节点，以及插入字符串、搜索字符串等操作。

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

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end

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

使用 Trie 类，可以插入字符串，搜索字符串，以及判断一个前缀是否是某个字符串的前缀。例如：

trie = Trie()

trie.insert("apple")
trie.insert("application")
trie.insert("banana")
trie.insert("band")

print(trie.search("apple"))  # True
print(trie.search("band"))   # True
print(trie.search("ap"))     # False
print(trie.starts_with("ap"))  # True

输出结果：

True
True
False
True

字典树的时间复杂度为 O(m)，其中 m 是字符串的长度。因此，字典树通常用于需要快速检索字符串的场合，如自动

相关文章