Trie树_字典树(字符串排序)简介及实现

接下来我将详细讲解“Trie树_字典树(字符串排序)简介及实现”的完整攻略。

什么是 Trie 树？

Trie 树，也叫字典树，是一种树形数据结构，用于处理字符串匹配、排序等问题。它的特点是能够快速地查找特定前缀或后缀的字符串。

Trie 树的基本实现

Trie 树通常是一棵多叉树，其中根节点不包含任何字符，每个子节点包含一个字符，组成一个完整的字符串。下面是一个简单的 Trie 树实现的示例代码：

class TrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.is_end_of_word = False

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

    def _char_to_index(self, ch):
        return ord(ch) - ord('a')

    def insert(self, word: str) -> None:
        node = self.root

        for ch in word:
            index = self._char_to_index(ch)
            if not node.children[index]:
                node.children[index] = TrieNode()
            node = node.children[index]

        node.is_end_of_word = True

    def search(self, word: str) -> bool:
        node = self.root

        for ch in word:
            index = self._char_to_index(ch)
            if not node.children[index]:
                return False
            node = node.children[index]

        return node.is_end_of_word

    def starts_with(self, prefix: str) -> bool:
        node = self.root

        for ch in prefix:
            index = self._char_to_index(ch)
            if not node.children[index]:
                return False
            node = node.children[index]

        return True

其中，TrieNode 类表示 Trie 树的节点，具有 children 和 is_end_of_word 两个属性。children 表示当前节点的子节点，由于字符集大小为 26，因此每个节点有 26 个子节点；is_end_of_word 表示当前节点所代表的字符串是否是一个单词的结尾。

Trie 类则表示 Trie 树本身，具有 root 属性。insert() 方法用于向 Trie 树中添加一个字符串；search() 方法用于查找一个字符串是否存在；starts_with() 方法用于查找是否存在以某个字符串为前缀的字符串。

Trie 树的应用

1.字符串匹配

Trie 树的一大应用是字符串匹配，可以快速地判断一个字符串是否包含另一个字符串。比如，我们可以用 Trie 树来实现敏感词过滤。

下面是一个简单的敏感词过滤的例子：

words = ["北京", "程序员", "公务员", "领导", "牛逼", "你妈"]

def is_contain_sensitive_word(sentence):
    trie = Trie()

    for word in words:
        trie.insert(word)

    for i in range(len(sentence)):
        j = i
        node = trie.root

        while j < len(sentence) and node.children[ord(sentence[j]) - ord('a')]:
            node = node.children[ord(sentence[j]) - ord('a')]
            j += 1

            if node.is_end_of_word:
                return True

    return False

该函数使用 Trie 树实现敏感词过滤。首先将所有敏感词添加到 Trie 树中，然后从字符串的第一个字符开始，依次检查每个字符能否与 Trie 树中的某个单词匹配，如果能够匹配，说明该字符串中包含敏感词。

2.字符串排序

Trie 树还可以用于字符串的排序。字符串排序是一种常见问题，可以通过建立 Trie 树来实现。

下面是一个简单的字符串排序的例子：

words = ["abc", "ab", "bcd", "cd", "a", "defg"]

class TrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.is_end_of_word = False
        self.words = []

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

    def _char_to_index(self, ch):
        return ord(ch) - ord('a')

    def insert(self, word: str) -> None:
        node = self.root

        for ch in word:
            index = self._char_to_index(ch)
            if not node.children[index]:
                node.children[index] = TrieNode()
            node = node.children[index]
            node.words.append(word)

        node.is_end_of_word = True

    def get_all_words(self):
        def dfs(node):
            if not node:
                return []
            res = []
            if node.is_end_of_word:
                res += node.words
            for child in node.children:
                if not child:
                    continue
                res += dfs(child)
            return res

        return dfs(self.root)

trie = Trie()

for word in words:
    trie.insert(word)

print(trie.get_all_words())

在 Trie 树上，每个节点都存储了当前路径上的所有字符串，依次递归 Trie 树，最后得到的即是排好序的字符串列表。

以上为 Trie 树的基本实现和应用，希望你能从中学到一些有用的知识。