您好,登錄后才能下訂單哦!
本篇內(nèi)容介紹了“Java怎么實(shí)現(xiàn)前綴樹”的有關(guān)知識(shí),在實(shí)際案例的操作過程中,不少人都會(huì)遇到這樣的困境,接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧!希望大家仔細(xì)閱讀,能夠?qū)W有所成!
字典樹(Trie樹)是一種樹形數(shù)據(jù)結(jié)構(gòu),常用于字符串的存儲(chǔ)和查找。字典樹的核心思想是利用字符串之間的公共前綴來節(jié)省存儲(chǔ)空間和提高查詢效率。它是一棵多叉樹,每個(gè)節(jié)點(diǎn)代表一個(gè)字符串的前綴,從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑組成一個(gè)字符串。
字典樹的根節(jié)點(diǎn)不包含字符,每個(gè)子節(jié)點(diǎn)代表一個(gè)字符,從根節(jié)點(diǎn)到任意一個(gè)節(jié)點(diǎn)所經(jīng)過的路徑上的字符連接起來即為該節(jié)點(diǎn)所代表的字符串。每個(gè)節(jié)點(diǎn)可以存儲(chǔ)一個(gè)或多個(gè)字符串,通常使用一個(gè)標(biāo)志來標(biāo)記一個(gè)節(jié)點(diǎn)代表的字符串是否存在。當(dāng)需要在一組字符串中查找某個(gè)字符串時(shí),可以利用字典樹來實(shí)現(xiàn)高效的查找操作。
例如對(duì)字符串?dāng)?shù)組{"goog","google","bai","baidu","a"}建立前綴樹,此時(shí)我們可以很清晰的看到前綴樹的一些特征:
根結(jié)點(diǎn)不保存字符
前綴樹是一顆多叉樹
前綴樹的每個(gè)節(jié)點(diǎn)保存一個(gè)字符
具有相同前綴的字符串保存在同一條路徑上
字符串的尾處相應(yīng)的在前綴樹上也有結(jié)束的標(biāo)志
力扣上的208題就是實(shí)現(xiàn)前綴樹:力扣
在寫代碼的時(shí)候,我偏向于用哈希表來存儲(chǔ)結(jié)點(diǎn)的信息,有的也可以用數(shù)組來存儲(chǔ)結(jié)點(diǎn)的信息,本質(zhì)上都是一樣的
public class Trie { Map<Character, Trie> next; boolean isEnd; public Trie() { this.next = new HashMap<>(); this.isEnd = false; } public void insert(String word) { } public boolean search(String word) { return false; } public boolean startsWith(String prefix) { return false; } }
public void insert(String word) { Trie trie = this;//獲得根結(jié)點(diǎn) for (char c : word.toCharArray()) { if (trie.next.get(c) == null) {//當(dāng)前結(jié)點(diǎn)不存在 trie.next.put(c, new Trie());//創(chuàng)建當(dāng)前結(jié)點(diǎn) } trie = trie.next.get(c);//得到字符c的結(jié)點(diǎn),繼續(xù)向下遍歷 } trie.isEnd = true; }
public boolean search(String word) { Trie trie = this;//獲得根結(jié)點(diǎn) for (char c : word.toCharArray()) { if (trie.next.get(c) == null) {//當(dāng)前結(jié)點(diǎn)不存在 return false; } trie = trie.next.get(c);//得到字符c的結(jié)點(diǎn),繼續(xù)向下遍歷 } return trie.isEnd; }
public boolean startsWith(String prefix) { Trie trie = this;//獲得根結(jié)點(diǎn) for (char c : prefix.toCharArray()) { if (trie.next.get(c) == null) {//當(dāng)前結(jié)點(diǎn)不存在 return false; } trie = trie.next.get(c);//得到字符c的結(jié)點(diǎn),繼續(xù)向下遍歷 } return true; }
接下來是力扣上關(guān)于前綴樹的一些題目
給出一個(gè)字符串?dāng)?shù)組words
組成的一本英語詞典。返回words
中最長的一個(gè)單詞,該單詞是由words
詞典中其他單詞逐步添加一個(gè)字母組成。
若其中有多個(gè)可行的答案,則返回答案中字典序最小的單詞。若無答案,則返回空字符串。
力扣:力扣
這是一道典型的前綴樹的問題,但是這一題有一些特殊的要求,返回的答案是:
1.最長的單詞
2.這個(gè)單詞由其他單詞逐步構(gòu)成
3.長度相同返回字典序小的
因此我們需要對(duì)前綴樹的相關(guān)代碼進(jìn)行修改,把字符串一一插入的代碼還是不改變的,主要修改的是查找的代碼,應(yīng)該在 trie.next.get(c) == null在增加一個(gè)判斷為false的條件,就是每一個(gè)結(jié)點(diǎn)都應(yīng)該有一個(gè)標(biāo)志true,表示每個(gè)節(jié)點(diǎn)都存在一個(gè)單詞,最終一步步構(gòu)成最長的單詞(葉子結(jié)點(diǎn)的單詞)
class Solution { public String longestWord(String[] words) { Trie trie = new Trie(); for (String word : words) { trie.insert(word); } String longest = ""; for (String word : words) { if (trie.search(word)) { if (word.length() > longest.length() || ((word.length() == longest.length()) && (word.compareTo(longest) < 0))) { longest = word; } } } return longest; } } class Trie { Map<Character, Trie> next; boolean isEnd; public Trie() { this.next = new HashMap<>(); this.isEnd = false; } public void insert(String word) { Trie trie = this;//獲得根結(jié)點(diǎn) for (char c : word.toCharArray()) { if (trie.next.get(c) == null) {//當(dāng)前結(jié)點(diǎn)不存在 trie.next.put(c, new Trie());//創(chuàng)建當(dāng)前結(jié)點(diǎn) } trie = trie.next.get(c);//得到字符c的結(jié)點(diǎn),繼續(xù)向下遍歷 } trie.isEnd = true; } public boolean search(String word) { Trie trie = this;//獲得根結(jié)點(diǎn) for (char c : word.toCharArray()) { if (trie.next.get(c) == null || !trie.next.get(c).isEnd) {//當(dāng)前結(jié)點(diǎn)不存在 return false; } trie = trie.next.get(c);//得到字符c的結(jié)點(diǎn),繼續(xù)向下遍歷 } return trie.isEnd; } }
“Java怎么實(shí)現(xiàn)前綴樹”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站,小編將為大家輸出更多高質(zhì)量的實(shí)用文章!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。