 Java实现)
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 回溯的经典结合需要我补充其中某个变体的实现吗
元宝 LeetCode 208. 实现 Trie (前缀树) Java实现
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 回溯的经典结合需要我补充其中某个变体的实现吗
