LeetCode 第208题：实现 Trie (前缀树)

题目描述

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

• Trie() 初始化前缀树对象。
• void insert(String word) 向前缀树中插入字符串 word。
• boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false。
• boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix，返回 true；否则，返回 false。

难度

中等

题目链接

点击在LeetCode中查看题目

示例

输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True

提示

• 1 <= word.length, prefix.length <= 2000
• word 和 prefix 仅由小写英文字母组成
• insert、search 和 startsWith 调用次数 总计 不超过 3 * 10^4 次

解题思路

Trie（前缀树或字典树）是一种专门处理字符串的树形数据结构，用于高效地存储和检索字符串。它的特点是：

1. 根节点不包含字符，除根节点外每个节点都只包含一个字符
2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串
3. 每个节点的所有子节点包含的字符都不相同

方法：Trie实现

1. 定义Trie节点结构，包含以下部分：

   • 子节点数组或映射（通常为26个小写字母）
   • 标志位表示是否为单词结尾

2. 实现插入操作(insert)：

   • 从根节点开始，逐个字符遍历单词
   • 对于每个字符，检查当前节点是否有对应的子节点
   • 如果没有，创建一个新的子节点
   • 移动到对应的子节点，继续处理下一个字符
   • 处理完最后一个字符后，标记当前节点为单词结尾

3. 实现查找操作(search)：

   • 从根节点开始，逐个字符遍历单词
   • 对于每个字符，检查当前节点是否有对应的子节点
   • 如果没有，返回false（单词不存在）
   • 如果有，移动到对应的子节点，继续处理下一个字符
   • 处理完最后一个字符后，检查当前节点是否被标记为单词结尾
   • 如果是，返回true；否则返回false

4. 实现前缀查找操作(startsWith)：

   • 与search操作类似，但不需要检查最后一个节点是否为单词结尾
   • 只要能够遍历完所有前缀字符，就返回true

时间复杂度：

• 插入操作：O(m)，其中m是单词长度
• 查找操作：O(m)
• 前缀查找操作：O(m)

空间复杂度：O(N*k)，其中N是单词总数，k是平均单词长度

代码实现

C# 实现

public class Trie {
    private class TrieNode {
        public TrieNode[] Children { get; }
        public bool IsEndOfWord { get; set; }
        
        public TrieNode() {
            Children = new TrieNode[26]; // 26个小写字母
            IsEndOfWord = false;
        }
    }
    
    private readonly TrieNode root;

    public Trie() {
        root = new TrieNode();
    }
    
    public void Insert(string word) {
        TrieNode current = root;
        
        foreach (char c in word) {
            int index = c - 'a';
            if (current.Children[index] == null) {
                current.Children[index] = new TrieNode();
            }
            current = current.Children[index];
        }
        
        current.IsEndOfWord = true;
    }
    
    public bool Search(string word) {
        TrieNode node = FindNode(word);
        return node != null && node.IsEndOfWord;
    }
    
    public bool StartsWith(string prefix) {
        return FindNode(prefix) != null;
    }
    
    private TrieNode FindNode(string prefix) {
        TrieNode current = root;
        
        foreach (char c in prefix) {
            int index = c - 'a';
            if (current.Children[index] == null) {
                return null;
            }
            current = current.Children[index];
        }
        
        return current;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.Insert(word);
 * bool param_2 = obj.Search(word);
 * bool param_3 = obj.StartsWith(prefix);
 */

Python 实现

class Trie:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

    def insert(self, word: str) -> None:
        current = self
        for c in word:
            if c not in current.children:
                current.children[c] = Trie()
            current = current.children[c]
        current.is_end_of_word = True

    def search(self, word: str) -> bool:
        node = self._find_node(word)
        return node is not None and node.is_end_of_word

    def startsWith(self, prefix: str) -> bool:
        return self._find_node(prefix) is not None
    
    def _find_node(self, prefix: str) -> 'Trie':
        current = self
        for c in prefix:
            if c not in current.children:
                return None
            current = current.children[c]
        return current

# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

C++ 实现

class Trie {
private:
    struct TrieNode {
        TrieNode* children[26];
        bool isEndOfWord;
        
        TrieNode() {
            for (int i = 0; i < 26; i++) {
                children[i] = nullptr;
            }
            isEndOfWord = false;
        }
        
        ~TrieNode() {
            for (int i = 0; i < 26; i++) {
                if (children[i] != nullptr) {
                    delete children[i];
                }
            }
        }
    };
    
    TrieNode* root;
    
    TrieNode* findNode(const string& prefix) {
        TrieNode* current = root;
        
        for (char c : prefix) {
            int index = c - 'a';
            if (current->children[index] == nullptr) {
                return nullptr;
            }
            current = current->children[index];
        }
        
        return current;
    }
    
public:
    Trie() {
        root = new TrieNode();
    }
    
    ~Trie() {
        delete root;
    }
    
    void insert(string word) {
        TrieNode* current = root;
        
        for (char c : word) {
            int index = c - 'a';
            if (current->children[index] == nullptr) {
                current->children[index] = new TrieNode();
            }
            current = current->children[index];
        }
        
        current->isEndOfWord = true;
    }
    
    bool search(string word) {
        TrieNode* node = findNode(word);
        return node != nullptr && node->isEndOfWord;
    }
    
    bool startsWith(string prefix) {
        return findNode(prefix) != nullptr;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

性能分析

各语言实现的性能对比：

实现语言	执行用时	内存消耗	特点
C#	156 ms	70.5 MB	使用数组存储子节点，直接索引访问
Python	128 ms	30.6 MB	使用字典存储子节点，更灵活
C++	36 ms	44.6 MB	最佳性能，手动内存管理

补充说明

代码亮点

1. C#和C++实现中使用数组存储子节点，通过字符减去’a’直接计算索引，访问效率高
2. Python实现使用字典存储子节点，适合处理更大的字符集
3. 抽取公共的FindNode方法，避免代码重复
4. C++实现中包含析构函数，确保正确释放内存

Trie树的优势

1. 前缀匹配：Trie树能够在O(m)时间内找到具有特定前缀的所有单词，其中m是前缀长度
2. 空间优化：共享前缀节点，减少存储空间
3. 字符串检索：相比哈希表，Trie树在前缀查找上有显著优势

实际应用

1. 自动补全功能
2. 拼写检查器
3. IP路由表查找
4. 文本预测（如T9键盘）
5. 字典实现

常见错误

1. 忘记标记单词结尾，导致search无法区分完整单词和前缀
2. 在startsWith方法中检查isEndOfWord
3. 内存管理不当，特别是在C++实现中
4. 索引计算错误，导致访问到错误的子节点

相关题目

• 211. 添加与搜索单词 - 数据结构设计
• 212. 单词搜索 II
• 648. 单词替换
• 677. 键值映射