前缀树(Trie)构建与应用(trie字典树)
1、前缀树介绍
前缀树(Trie树),即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。
典型应用是用于 统计 和 排序 大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。
优点:最大限度地减少无谓的字符串比较,查询效率比哈希表高。
以下介绍图源于网络
2、前缀树应用(剑指 Offer 替换单词)
在英语中,有一个叫做 词根(root) 的概念,它可以跟着其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如,词根an,跟随着单词 other(其他),可以形成新的单词 another(另一个)。现在,给定一个由许多词根组成的词典和一个句子,需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根,则用最短的词根替换它。需要输出替换之后的句子。
示例1
输入: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery" 输出: "the cat was rat by the bat"复制代码
示例2
输入:dictionary = ["ac","ab"], sentence = "it is abnormal that this solution is accepted" 输出: "it is ab that this solution is ac"复制代码
实现代码以及注释
class Solution { class TreeNode { // 构建前缀树节点 TreeNode[] kids; // 指向的孩子节点 boolean word = false; public TreeNode() { kids = new TreeNode[26]; } } TreeNode root = new TreeNode(); public String replaceWords(List<String> dictionary, String sentence) { String[] dicts = dictionary.toArray(new String[dictionary.size()]); String[] words = sentence.split(" "); for (String s : dicts) { buildTree(s); // 建立前缀树 } StringBuilder sb = new StringBuilder(); for (String s : words) { sb.append(find(s)); // 寻找符合的前缀单词 sb.append(" "); } sb.deleteCharAt(sb.length() - 1); return sb.toString(); } private void buildTree(String s) { char[] cs = s.toCharArray(); TreeNode node = root; for (char c : cs) { if (node.kids[c - 'a'] == null) { node.kids[c - 'a'] = new TreeNode(); // 若是该节点为空,则为它分配一个孩子节点 } node = node.kids[c - 'a']; // 当前节点指向下一个目标节点 } node.word = true; // 标志着此处为前缀树单词结束位置 } private String find(String s) { char[] cs = s.toCharArray(); TreeNode node = root; int p = 0; for (char c : cs) { if (node.word == true) return s.substring(0,p); // 前缀树结束单词最后一个字母,返回 s[0,p) 即可 if (node.kids[c - 'a'] == null) return s; node = node.kids[c - 'a']; p++; } return s.substring(0,p); } }
伪原创工具 SEO网站优化 https://www.237it.com/
作者:onv
链接:https://juejin.cn/post/7035475721812181000