Day 67

題目描述

思路

初次思路：此時(shí)還不了解什么是前綴樹，嘗試自己實(shí)現(xiàn)一下
由于我們需要快速定位前綴和字符串，于是我想到了使用hashset實(shí)現(xiàn)，tes用于存放字符串，prefixs存放前綴，獲取前綴通過(guò)使用substring進(jìn)行拆分。

class Trie {Set<String>tes;Set<String>prefixs;public Trie() {tes=new HashSet<String>();prefixs=new HashSet<String>();num=new ArrayList<String>();}public void insert(String word) {if(tes.contains(word)){return;}else{tes.add(word);for(int i=0;i<=word.length();i++){String a=word.substring(0,i);prefixs.add(a);}}}public boolean search(String word) {return tes.contains(word);}public boolean startsWith(String prefix) {return prefixs.contains(prefix);}
}/*** Your Trie object will be instantiated and called as such:* Trie obj = new Trie();* obj.insert(word);* boolean param_2 = obj.search(word);* boolean param_3 = obj.startsWith(prefix);*/

學(xué)習(xí)前綴樹后：
前綴樹的作用在于快速檢索字符串的前綴，插入一個(gè)字符串，即為從根一次插入孩子節(jié)點(diǎn)，將字符串最后一個(gè)字符對(duì)應(yīng)的節(jié)點(diǎn)標(biāo)記結(jié)束節(jié)點(diǎn)，再插入另外一個(gè)相同前綴但最后n個(gè)字符不一樣的字符串，那么在相同前綴的部分，不需要插入新的節(jié)點(diǎn)，直到第一個(gè)不同的字符，添加一個(gè)新的子節(jié)點(diǎn)。
這樣做的好處，我們?nèi)绻@取兩個(gè)字符串的前綴，只需要從根節(jié)點(diǎn)向下遍歷，比較兩個(gè)字符串，只要到某個(gè)節(jié)點(diǎn)出現(xiàn)了分支，則這個(gè)節(jié)點(diǎn)之前的節(jié)點(diǎn)就是兩個(gè)字符的公共前綴。同時(shí)節(jié)約了存儲(chǔ)空間
做法如下：

class Trie {public Trie[]child;//孩子節(jié)點(diǎn)，可能插入的是26個(gè)英文字母中的一個(gè)public boolean isend;//判斷是否為一個(gè)字符串的結(jié)束 區(qū)分前綴和字符串public Trie() {child=new Trie[26];isend=false;}public void insert(String word) {Trie node=this;//根節(jié)點(diǎn)for(int i=0;i<word.length();i++){char a=word.charAt(i);int index=a-'a';//轉(zhuǎn)化為序號(hào)if(node.child[index]==null){node.child[index]=new Trie();//創(chuàng)建為新孩子}node=node.child[index];//移動(dòng)到下一個(gè)孩子}node.isend=true;//將結(jié)束標(biāo)志置為true}public boolean search(String word) {Trie node=searchPrefix(word);if(node!=null&&node.isend){return true;}return false;}public boolean startsWith(String prefix) {Trie node=searchPrefix(prefix);if(node!=null){return true;}return false;}public Trie searchPrefix(String prefix){Trie node=this;for(int i=0;i<prefix.length();i++){char a=prefix.charAt(i);int index=a-'a';if(node.child[index]==null){//還沒遍歷完前綴就結(jié)束了 說(shuō)明找不到return null;}node=node.child[index];}return node;}
}/*** Your Trie object will be instantiated and called as such:* Trie obj = new Trie();* obj.insert(word);* boolean param_2 = obj.search(word);* boolean param_3 = obj.startsWith(prefix);*/