企业官网建设流程全解析

LeetCode 208. 实现 Trie（前缀树）Java 实现

题目简述

实现一个 Trie（前缀树），支持三种操作：

操作 含义

“insert(word)” 插入字符串

“search(word)” 查找完整字符串是否存在

“startsWith(prefix)” 查找是否有以 prefix 为前缀的字符串

核心思想

每个节点包含一个
“children[26]”（对应 a~z）和一个
“isEnd” 标记（表示是否是某个单词的结尾）。

root / | \ a b ... / \ p ...

/
p ← isEnd = true (“app”)

Java 实现

class Trie {

// Trie 节点定义 private static class TrieNode { TrieNode[] children = new TrieNode[26]; boolean isEnd; // 标记是否为某个单词的结尾 } private final TrieNode root; // 初始化 Trie public Trie() { root = new TrieNode(); } // 插入单词 public void insert(String word) { TrieNode node = root; for (char c : word.toCharArray()) { int index = c - 'a'; if (node.children[index] == null) { node.children[index] = new TrieNode(); } node = node.children[index]; } node.isEnd = true; // 标记单词结尾 } // 查找完整单词是否存在 public boolean search(String word) { TrieNode node = searchPrefix(word); return node != null && node.isEnd; } // 查找是否有以 prefix 为前缀的单词 public boolean startsWith(String prefix) { return searchPrefix(prefix) != null; } // 公共辅助方法：沿 prefix 走到最后一个节点 private TrieNode searchPrefix(String prefix) { TrieNode node = root; for (char c : prefix.toCharArray()) { int index = c - 'a'; if (node.children[index] == null) { return null; } node = node.children[index]; } return node; }

}

使用示例

Trie trie = new Trie();
trie.insert(“apple”);
trie.search(“apple”); // true
trie.search(“app”); // false（“app” 不是完整单词）
trie.startsWith(“app”); // true
trie.insert(“app”);
trie.search(“app”); // true

复杂度分析

操作 时间复杂度 空间复杂度

“insert” O(m)，m 为单词长度 O(m)

“search” O(m) O(1)

“startsWith” O(m) O(1)

关键要点

“isEnd” 标记不能省：区分
““app”” 是前缀还是完整单词
2.
“searchPrefix” 抽取公共逻辑：
“search” 和
“startsWith” 都复用，代码更简洁
3. 数组大小固定 26：因为题目限定只有小写字母 a~z
4. 如果用 HashMap 代替数组：可以支持任意字符集（Unicode），但常数开销更大

常见变体

• 支持
  “delete” 操作：需要回溯标记，较复杂
• 统计以某前缀开头的单词数量：在节点加
  “count” 字段
• LeetCode 211. 添加与搜索单词：在 search 中加入
  “.” 通配符匹配（需 DFS）
• LeetCode 212. 单词搜索 II：Trie + 回溯的经典结合

需要我补充其中某个变体的实现吗？