汇鑫网站建设,个人网站论坛展示,wordpress整站源码带数据,阿里云 网站空间文章目录 1、背景2、前缀树Trie3、leetcode208#xff1a;实现Trie4、leetcode720#xff1a;词典中最长的单词 1、背景 如上#xff0c;以浏览器搜索时的自动匹配为例#xff1a; 如果把所有搜索关键字放一个数组里#xff0c;则#xff1a;插入、搜索一个词条时#x… 文章目录 1、背景2、前缀树Trie3、leetcode208实现Trie4、leetcode720词典中最长的单词 1、背景 如上以浏览器搜索时的自动匹配为例 如果把所有搜索关键字放一个数组里则插入、搜索一个词条时时间复杂度为O(n)判断某个前缀是否存在时间复杂度为O(n × mm为词条长度因为在遍历数组时要挨个对比数组每个元素的每个字符和词条前缀的每个字符是否相同得两层for循环时间复杂度太高比如在以下数组判断是否有前缀为haha的关键字
[googgooglgooglebaibaidugi]2、前缀树Trie
前缀树又叫字典树是一种数据结构Trie发音类似 “try”。比如存以下这些数据到前缀树
googgooglgooglebaibaidugi效果 root节点一般不存数据其下有孩子节点。以goog为例存到第二个g时这个单词没了此时这儿所在的节点会有一个结束的Flag以及该Flag处对应的值。从以上的分析大致可以看出前缀树Trie这种结构其对象应该有以下属性
孩子节点children某个单词的结束标志isEnd
关于时间复杂度如果输入字符串str其长度为k
插入O(k)搜索O(k)判断是否存在str这个前缀的词语O(k)
关于前缀树这种结构的应用场景
前缀匹配词频统计做统计当然也可用HashMap实现
3、leetcode208实现Trie
以英语单词为例26个字母根据ASCII码转为数字就是数组的下标。Trie类应该有个isEnd属性因为要区分
是否有str这个单词是否有以str开头为前缀的单词
比较到str的最后一个字母isEnd为true说明有str这个单词是否有这个前缀则不用考虑isEnd。
此外正常来说每个Trie节点的值val也要存一下但对英文字母不用因为其对应的SSCII码可以当下标下标转一下就是字母值。 参照以上示意图每个节点上存着一个字母索引与ASCII码写前缀树的实现
public class Trie {private Trie[] children;private boolean isEnd;public Trie() {// 26个英文字母每个节点最多26个儿子节点children new Trie[26];isEnd false;}public void insert(String word) {// 调用insert方法的对象可认为是根节点Trie node this;for (int i 0; i word.length(); i) {char ch word.charAt(i);// 字母转ASCII码a对应97减去a可让值从0开始而不是97方便对应数组下标int index ch - a;if (node.children[index] null) {// 这是个新字母创建一个新的节点作为子节点// 这个节点对应的字母的值不用存下标97转回去就是这个节点的值node.children[index] new Trie();}// 该判断word里的下一个字母了node节点不再是根节点而是第一个字母的对应的节点node node.children[index];}// 整个word都遍历完了结束标志为置为truenode.isEnd true;}public boolean search(String word) {Trie node this;for (int i 0; i word.length(); i) {char ch word.charAt(i);// 字母转ASCII码a对应97减去a可让值从0开始而不是97方便对应数组下标int index ch - a; if (node.children[index] null) {// 往下顺如果有字母不一样说明一定不存在这个单词return false;}// 检查下一个字母替换下Tire节点node node.children[index];}// 和判断前缀是否存在不一样搜索找到末尾后末尾这儿必须有单词的结束标志isEndreturn node.isEnd;}public boolean startsWith(String prefix) {Trie node this;for (int i 0; i prefix.length(); i) {char ch prefix.charAt(i);// 字母转ASCII码a对应97减去a可让值从0开始而不是97方便对应数组下标int index ch - a;if (node.children[index] null) {return false;}// 检查下一个字母替换下Tire节点node node.children[index];}return true;}
}搜索和判断前缀的代码重复度太高优化下抽取公共代码
public class Trie {private Trie[] children;private boolean isEnd;public Trie() {// 26个英文字母每个节点最多26个儿子节点children new Trie[26];isEnd false;}public void insert(String word) {// 调用insert方法的对象可认为是根节点Trie node this;for (int i 0; i word.length(); i) {char ch word.charAt(i);// 字母转ASCII码a对应97减去a可让值从0开始而不是97方便对应数组下标int index ch - a;if (node.children[index] null) {// 这是个新字母创建一个新的节点作为子节点// 这个节点对应的字母的值不用存下标97转回去就是这个节点的值node.children[index] new Trie();}// 该判断word里的下一个字母了node节点不再是根节点而是第一个字母的对应的节点node node.children[index];}// 整个word都遍历完了结束标志为置为truenode.isEnd true;}/*** 搜索和判断前缀是否存在两个操作的公共逻辑抽取** param str 输入的字符串* return 返回最后一个字母对应的Trie节点无则返回null*/public Trie getTrieNode(String str) {if (str null) {return null;}// 调用insert方法的对象可认为是根节点Trie node this;for (int i 0; i str.length(); i) {char ch str.charAt(i);// 字母转ASCII码a对应97减去a可让值从0开始而不是97方便对应数组下标int index ch - a;if (node.children[index] null) {// 往下顺如果有字母不一样说明一定不存在这个单词或前缀return null;}// 检查str的下一个字母替换下Tire节点node node.children[index];}return node;}public boolean search(String word) {Trie trieNode getTrieNode(word);// 和判断前缀是否存在不一样搜索找到末尾后末尾这儿必须有单词的结束标志isEndreturn trieNode ! null trieNode.isEnd;}public boolean startsWith(String prefix) {return getTrieNode(prefix) ! null;}
}从优化后的代码可以看到搜索和判断前缀的区别是判断到输入字符的最后一个字母后搜索要有isEnd标志为true表示有这样的单词以免出现搜abc但只有abcd时也返回true的情况。而判断前缀是否存在则不用考虑这个标志位。
4、leetcode720词典中最长的单词 如题中示例1能返回world需要前面有w ⇒ wo ⇒ wor ⇒ worl这四个词语才行 将题中数组的每个单词存入前缀树然后遍历数组。比如app单词a字母找到了且isEnd为true往下ap也找到了且isEnd为true如此app这个单词就是目前符合要求的。
public class P720 {public String longestWord(String[] words) {if (null words || words.length 0) {return ;}Trie trie new Trie();for (String word : words) {trie.insert(word);}String result ;// 控制精确跳到外层循环而不是内层outerLoop:for (String word : words) {String temp ;for (String s : word.split()) {temp temp s;if (!trie.search(temp)) {// 如果有一个字母找不到则直接看题中数组里的下一个单词continue outerLoop;}}// 判断完一个单词符号要求后如果长度超过了result则替换if (word.length() result.length()) {result word;} else if (word.length() result.length()) {// 如果判断完一个单词符号要求后如果长度等于result则对比取字典序小的// compareToIgnoreCase() 方法与 compareTo() 方法类似但会忽略大小写result word.compareToIgnoreCase(result) 0 ? word : result;}}return result;}
}
以上套用了208题的Trie类的search方法search方法只判断搜到末尾时isEnd是否为true即它只关心有没有world这个词而不关心有没有w ⇒ wo ⇒ wor ⇒ worl这四个词语isEnd为true再修改下search方法
public class Trie {private Trie[] children;private boolean isEnd;//略同上一题/*** 搜索是否有word单词以及w ⇒ wo ⇒ wor ⇒ worl这四个单词*/public boolean searchByStep(String word) {if (word null) {return false;}// 根节点Trie node this;for (int i 0; i word.length(); i) {char ch word.charAt(i);int index ch - a;// 没有这个字母或者这地方结束标志为false则返回falseif (node.children[index] null || !node.children[index].isEnd) {return false;}// 检查str的下一个字母替换下Tire节点node node.children[index];}// 到最后一个字母所在的节点了return node ! null node.isEnd;}
}用新的前缀树搜索方法判断word是否存在的同时还要判断w ⇒ wo ⇒ wor ⇒ worl这四个是否存在并简化下实现代码
public class P720 {public String longestWord(String[] words) {if (null words || words.length 0) {return ;}Trie trie new Trie();for (String word : words) {trie.insert(word);}String result ;for (String word : words) {// 不符合条件判断下一个单词if (!trie.searchByStep(word)) {continue;}// 判断完一个单词符合要求后如果长度超过了result则替换// 如果判断完一个单词符号要求后如果长度等于result则对比取字典序小的替换result// compareToIgnoreCase() 方法与 compareTo() 方法类似但会忽略大小写if (word.length() result.length() || (word.length() result.length()) word.compareToIgnoreCase(result) 0) {result word;} }return result;}
}
