字典树在LeetCode中的应用与解析

字典树（Trie树）是一种高效的字符串匹配数据结构，广泛应用于文本检索、自动补全、拼写检查等领域。在LeetCode平台上，字典树的题目不仅考察了数据结构的基本原理，还测试了算法的优化能力。本文将详细介绍字典树的基本概念、在LeetCode中的应用以及相关题目的解法。

字典树的基本概念

字典树，又称前缀树，是一种有序树，用于存储关联数组，其键通常是字符串。与二叉查找树不同，字典树的每个节点不存储整个键，而是存储键中的一个字符。字典树的优点在于：

高效的字符串检索：查找、插入和删除操作的时间复杂度为O(m)，其中m是键的长度。
前缀匹配：可以快速找到所有以某个前缀开头的字符串。
空间效率：通过共享公共前缀，可以节省存储空间。

字典树在LeetCode中的应用

在LeetCode中，字典树常见于以下几类题目：

字符串匹配：
- LeetCode 208. Implement Trie (Prefix Tree)：实现一个字典树，支持插入、查找和前缀匹配。
- LeetCode 211. Design Add and Search Words Data Structure：设计一个支持添加单词、搜索单词和通配符搜索的数据结构。
前缀匹配：
- LeetCode 648. Replace Words：给定一个字典和一个句子，将句子中的单词替换为其最短前缀。
- LeetCode 676. Implement Magic Dictionary：实现一个“魔法字典”，支持添加单词和搜索单词（允许一个字符的错误）。
单词游戏：
- LeetCode 472. Concatenated Words：找出所有可以由字典中的单词拼接而成的单词。
- LeetCode 720. Longest Word in Dictionary：找出字典中最长的单词，该单词可以由其他单词拼接而成。

字典树的实现与优化

在实现字典树时，需要注意以下几点：

节点结构：每个节点包含一个字符和一个指向子节点的指针数组（通常是26个字母）。
插入操作：从根节点开始，逐字符插入，创建不存在的节点。
查找操作：从根节点开始，逐字符匹配，找到匹配的单词或前缀。
优化：可以使用压缩字典树（Patricia Trie）来减少节点数量，提高空间效率。

LeetCode题目解析

LeetCode 208. Implement Trie (Prefix Tree)：

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

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

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

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

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

LeetCode 211. Design Add and Search Words Data Structure：

class WordDictionary:
    def __init__(self):
        self.trie = {}

    def addWord(self, word: str) -> None:
        node = self.trie
        for char in word:
            if char not in node:
                node[char] = {}
            node = node[char]
        node['$'] = True

    def search(self, word: str) -> bool:
        def dfs(node, index):
            if index == len(word):
                return '$' in node
            if word[index] == '.':
                for child in node.values():
                    if dfs(child, index + 1):
                        return True
            elif word[index] in node:
                return dfs(node[word[index]], index + 1)
            return False
        return dfs(self.trie, 0)

总结

字典树在LeetCode中的应用不仅体现了其在字符串处理方面的优势，还展示了如何通过数据结构的优化来提高算法效率。通过学习和实践这些题目，可以更好地理解字典树的原理和应用场景，提升编程能力和算法思维。希望本文能为大家提供一个清晰的指导，帮助大家在LeetCode中更好地解决字典树相关的问题。