博客

Python实现简单字典树的方法

  • Post category:Python

Python实现简单字典树的方法

什么是字典树？

字典树（Trie）是一种树形数据结构，用于高效地存储和查找字符串数据集中的键值。字典树有一个根节点，每个节点可以有多个子节点，子节点代表了该节点所代表的字符。从根节点到每个叶子节点的路径上表示了一个字符串，因此字典树常用于字符串的模式匹配和前缀搜索。

代码实现

我们可以使用Python来实现一个简单的字典树。首先我们定义一个TrieNode类表示一个节点，它有两个属性：子节点和一个标志标记该节点是否为一个单词的末尾。

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

下面我们定义一个Trie类，表示整个字典树，它有两个方法：添加单词和查找单词。

添加单词

我们可以使用一个循环依次遍历每个字符，在字典树中查找是否已经存在该字符的节点。如果没有，就新建节点并将其加入到父节点中。处理完整个单词后，将末尾的节点标记为单词的末尾。

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

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

查找单词

与添加单词类似，我们在字典树中遍历每个字符，如果不存在该字符的节点，就说明该单词不在字典树中。如果遍历完所有字符后，最后一个节点是一个单词的末尾，就说明该单词存在于字典树中。

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

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

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

示例说明

示例1：添加单词和查找单词

我们可以使用以下代码创建一个字典树，添加单词”apple”和”orange”，并查找单词”apple”和”banana”。

trie = Trie()
trie.insert("apple")
trie.insert("orange")
print(trie.search("apple")) # True
print(trie.search("banana")) # False

输出结果为：

True
False

示例2：查找单词的前缀

字典树也常用于查找单词的前缀，我们可以使用类似的方式在字典树中遍历前缀，并输出所有以该前缀为前缀的单词。

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

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

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

    def startsWith(self, prefix: str) -> List[str]:
        node = self.root
        for c in prefix:
            if c not in node.children:
                return []
            node = node.children[c]
        return self._dfs(node, prefix)

    def _dfs(self, node, prefix):
        res = []
        if node.isword:
            res.append(prefix)
        for c, child in node.children.items():
            res += self._dfs(child, prefix+c)
        return res

我们可以使用以下代码创建一个字典树，添加单词”apple”和”orange”，并输出所有以前缀”app”为前缀的单词。

trie = Trie()
trie.insert("apple")
trie.insert("orange")
print(trie.startsWith("app")) # ["apple"]

输出结果为：

["apple"]

以上便是一个简单字典树的实现方法，大家可以根据实际需求进行拓展和改进。

Tags: ,