208. 实现 Trie (前缀树) Medium

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

请你实现 Trie 类：

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

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

示例 2：
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

解题思路

输入：一个整数数组 nums，元素可能有正有负

输出：找出所有不重复的三元组 [a, b, c]，满足 a + b + c == 0

本题是典型的 前缀树 Trie 问题。

        (root)
    / / / | \ \ \ 
   a s x  f  z p b 
   ...

Trie 是一种树形结构，用于高效地存储和检索字符串集合。

1. 核心思想：

• 每个节点代表一个字符。
• 每条路径代表一个前缀。
• 在单词的最后一个字符处，用一个标记（如 isWord = true）来区分“完整单词”与“只是前缀”

2. 操作逻辑

   • insert(word)：逐字符建节点，最后标记 isWord=true。
   • search(word)：逐字符查找，最后必须 isWord=true 才返回 true。
   • startsWith(prefix)：逐字符查找，只要路径存在就返回 true。

3. 复杂度

   • 插入 / 查找 / 前缀判断：O(m)，m 为字符串长度。
   • 空间换时间。

代码实现

python

class Trie:

    def __init__(self):
        # 初始化一个空字典，用于表示 Trie 的根节点
        self.trie = {}
        
    def insert(self, word: str) -> None:
        # 从 Trie 的根节点开始插入单词
        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:
        # 从 Trie 的根节点开始搜索单词
        node = self.trie
        for char in word:
            # 如果当前字符在节点中未找到，返回 False
            if char not in node:
                return False
            # 移动到下一个节点
            node = node[char]
        # 检查当前节点是否标记为单词的结束
        return '#' in node

    def startsWith(self, prefix: str) -> bool:
        # 从 Trie 的根节点开始检查前缀
        node = self.trie
        for char in prefix:
            # 如果当前字符在节点中未找到，返回 False
            if char not in node:
                return False
            # 移动到下一个节点
            node = node[char]
        # 如果循环结束，说明前缀存在
        return True

javascript

// 定义 Trie（前缀树 / 字典树）
class Trie {
    constructor() {
        // 根节点，用 Map 存储子节点
        this.root = {};
    }

    /** 
     * 插入一个单词到 Trie 中
     * @param {string} word
     * @return {void}
     */
    insert(word) {
        let curr = this.root;
        for (let ch of word) {
            // 如果当前节点没有该字符，则新建一个子节点
            if (!curr[ch]) {
                curr[ch] = {};
            }
            // 移动到子节点
            curr = curr[ch];
        }
        // 标记该路径为一个完整单词
        curr.isWord = true;
    }

    /** 
     * 判断 Trie 中是否存在完整的单词 word
     * @param {string} word
     * @return {boolean}
     */
    search(word) {
        let curr = this.root;
        for (let ch of word) {
            // 如果找不到该字符，返回 false
            if (!curr[ch]) return false;
            curr = curr[ch];
        }
        // 必须是完整单词
        return !!curr.isWord;
    }

    /** 
     * 判断 Trie 中是否存在以 prefix 为前缀的路径
     * @param {string} prefix
     * @return {boolean}
     */
    startsWith(prefix) {
        let curr = this.root;
        for (let ch of prefix) {
            if (!curr[ch]) return false;
            curr = curr[ch];
        }
        return true;
    }
}

复杂度分析

时间复杂度：O(m) 取决于搜索的字符串长度

空间复杂度：O(m) 取决于字符类型的数量

链接

208 国际版

208 中文版