领地免费网站程序,wordpress 页面添加js,随州网站建设哪家实惠,微信放在网站根目录字典树#xff08;前缀树#xff09; 208. 实现 Trie (前缀树)题目描述示例知识补充官解代码 211. 添加与搜索单词 - 数据结构设计题目描述示例思路Java代码 208. 实现 Trie (前缀树)
力扣链接#xff1a;208. 实现 Trie (前缀树)
题目描述 示例 知识补充 插入字符串
我… 字典树前缀树 208. 实现 Trie (前缀树)题目描述示例知识补充官解代码 211. 添加与搜索单词 - 数据结构设计题目描述示例思路Java代码 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;}
}
