保定网站制作企业,jeecms可以做网站卖吗,电商运营八大流程,网站制作方案包括哪些内容我一开始想题目叫前缀树#xff0c;是要用树吗#xff1f;但是不知道用树怎么写#xff0c;然后我就花了10多分钟#xff0c;用了HashMap解了。map的key是word#xff0c;value是一个放了word的所有前缀的set#xff0c;这样search方法就非常简单了#xff0c;只要看has…
我一开始想题目叫前缀树是要用树吗但是不知道用树怎么写然后我就花了10多分钟用了HashMap解了。map的key是wordvalue是一个放了word的所有前缀的set这样search方法就非常简单了只要看hashmap里面有没有这个key就行startsWith方法就很垃圾了我遍历了所有的value如果其中一个value中有这个前缀就返回true遍历完了返回false以下是我的代码
class Trie {private HashMapString, SetString map;public Trie() {map new HashMap();}public void insert(String word) {int n word.length();SetString set new HashSet();int i n;while(i0){String str word.substring(0,i);set.add(str);i--;}map.put(word, set);}public boolean search(String word) {return map.containsKey(word);}public boolean startsWith(String prefix) {Set keyset map.keySet();Iterator iterator keyset.iterator();while(iterator.hasNext()){String key (String)iterator.next();if(map.get(key).contains(prefix)){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 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;}
} 它这个树的结构非常巧妙节点Trie表示一个小写字母每个节点都包含一个标致位boolean isEnd,表示这个小写字母是不是某个单词的结束字母还包含一个节点数组Trie[] childernchildren[0]表示‘a’..children[25]表示‘z’。
所以比如apple这个单词可以通过字典树表示如下 如果再往里面加两个单词app和yel就会变成这样 p的isEnd变成了true加了一个单词“yel”这样就非常方便查找了。
public Trie() {children new Trie[26];isEnd false;}
通过构造方法我们可以看出节点创建的时候它的isEnd是falsechildre只是创建了一个数组容器数组里面的节点是没有创建的。
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;}
insert方法非常简单就是遍历这个word把它的每个字母往后面添加最后一个字母的isEnd设置成true。
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;}
searchPrefix()方法作为一个辅助方法作用是找到传进来的这个单词的最后一个字母。 public boolean search(String word) {Trie node searchPrefix(word);return node ! null node.isEnd;}
search()调用searchPrefix()方法拿到单词的最后一个字母节点如果这个节点不为空并且是结束返回true。 public boolean startsWith(String prefix) {return searchPrefix(prefix) ! null;}startsWith()方法调用searchPrefix()方法找到前缀的最后一个字母节点只要这个节点不为空就返回true。
这个字典树的方法是非常的巧妙。
