OJ练习第182题——字典树（前缀树）

208. 实现 Trie (前缀树)

力扣链接：208. 实现 Trie (前缀树)

题目描述

示例

知识补充

插入字符串

我们从字典树的根开始，插入字符串。对于当前字符对应的子节点，有两种情况：

子节点存在。沿着指针移动到子节点，继续处理下一个字符。
子节点不存在。创建一个新的子节点，记录在 children 数组的对应位置上，然后沿着指针移动到子节点，继续搜索下一个字符。

重复以上步骤，直到处理字符串的最后一个字符，然后将当前节点标记为字符串的结尾。

查找前缀

我们从字典树的根开始，查找前缀。对于当前字符对应的子节点，有两种情况：

子节点存在。沿着指针移动到子节点，继续搜索下一个字符。
子节点不存在。说明字典树中不包含该前缀，返回空指针。
重复以上步骤，直到返回空指针或搜索完前缀的最后一个字符。

若搜索到了前缀的末尾，就说明字典树中存在该前缀。此外，若前缀末尾对应节点的 isEnd 为真，则说明字典树中存在该字符串。

官解代码

class Trie {private Trie[] children;private boolean isEnd;public Trie() {children = new Trie[26];isEnd = false;}public void insert(String word) {Trie node = this;for (int i = 0; i < word.length(); i++) {char ch = word.charAt(i);int index = ch - 'a';if (node.children[index] == null) {node.children[index] = new Trie();}node = node.children[index];}node.isEnd = true;}public boolean search(String word) {Trie node = searchPrefix(word);return node != null && node.isEnd;}public boolean startsWith(String prefix) {return searchPrefix(prefix) != null;}private Trie searchPrefix(String prefix) {Trie node = this;for (int i = 0; i < prefix.length(); i++) {char ch = prefix.charAt(i);int index = ch - 'a';if (node.children[index] == null) {return null;}node = node.children[index];}return node;}
}作者：力扣官方题解
链接：https://leetcode.cn/problems/implement-trie-prefix-tree/solutions/717239/shi-xian-trie-qian-zhui-shu-by-leetcode-ti500/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

211. 添加与搜索单词 - 数据结构设计

力扣链接：211. 添加与搜索单词 - 数据结构设计

题目描述

示例

思路

根据题意，WordDictionary 类需要支持添加单词和搜索单词的操作，可以使用字典树实现。

对于添加单词，将单词添加到字典树中即可。

对于搜索单词，从字典树的根结点开始搜索。由于待搜索的单词可能包含点号，因此在搜索过程中需要考虑点号的处理。对于当前字符是字母和点号的情况，分别按照如下方式处理：

如果当前字符是字母，则判断当前字符对应的子结点是否存在，如果子结点存在则移动到子结点，继续搜索下一个字符，如果子结点不存在则说明单词不存在，返回 false；

如果当前字符是点号，由于点号可以表示任何字母，因此需要对当前结点的所有非空子结点继续搜索下一个字符。

重复上述步骤，直到返回 false 或搜索完给定单词的最后一个字符。

如果搜索完给定的单词的最后一个字符，则当搜索到的最后一个结点的 isEnd 为 true 时，给定的单词存在。

特别地，当搜索到点号时，只要存在一个非空子结点可以搜索到给定的单词，即返回 true。

Java代码

class WordDictionary {private Trie root;public WordDictionary() {root = new Trie();}public void addWord(String word) {root.insert(word);}public boolean search(String word) {return dfs(word, 0, root);}private boolean dfs(String word, int index, Trie node) {if(index == word.length()) {return node.isEnd();}char ch = word.charAt(index);if(Character.isLetter(ch)) {int childIndex = ch - 'a';Trie child = node.getChildren()[childIndex];if(child != null && dfs(word, index + 1, child)) {return true;}}else {for(int i = 0; i < 26; i++) {Trie child = node.getChildren()[i];if(child != null && dfs(word, index + 1, child)) {return true;}}}return false;}
}
class Trie {private Trie[] children;private boolean isEnd;public Trie() {children = new Trie[26];isEnd = false;}public void insert(String word) {Trie node = this;for(int i = 0; i < word.length(); i++) {char ch = word.charAt(i);int index = ch - 'a';if(node.children[index] == null) {node.children[index] = new Trie();}node = node.children[index];}node.isEnd = true;}public Trie[] getChildren() {return children;}public boolean isEnd() {return isEnd;}
}