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”); // truetrie.search(“app”); // false“app” 不是完整单词trie.startsWith(“app”); // truetrie.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~z4. 如果用 HashMap 代替数组可以支持任意字符集Unicode但常数开销更大常见变体支持“delete” 操作需要回溯标记较复杂统计以某前缀开头的单词数量在节点加“count” 字段LeetCode 211. 添加与搜索单词在 search 中加入“.” 通配符匹配需 DFSLeetCode 212. 单词搜索 IITrie 回溯的经典结合需要我补充其中某个变体的实现吗