字典樹的根節(jié)點不包含字符，每個子節(jié)點代表一個字符，從根節(jié)點到任意一個節(jié)點所經過的路徑上的字符連接起來即為該節(jié)點所代表的字符串。每個節(jié)點可以存儲一個或多個字符串，通常使用一個標志來標記一個節(jié)點代表的字符串是否存在。當需要在一組字符串中查找某個字符串時，可以利用字典樹來實現(xiàn)高效的查找操作。

2.前綴樹的舉例

例如對字符串數(shù)組{"goog","google","bai","baidu","a"}建立前綴樹,此時我們可以很清晰的看到前綴樹的一些特征:

根結點不保存字符
前綴樹是一顆多叉樹
前綴樹的每個節(jié)點保存一個字符
具有相同前綴的字符串保存在同一條路徑上
字符串的尾處相應的在前綴樹上也有結束的標志

二.前綴樹的實現(xiàn)

力扣上的208題就是實現(xiàn)前綴樹:力扣

1.前綴樹的數(shù)據(jù)結構

在寫代碼的時候,我偏向于用哈希表來存儲結點的信息,有的也可以用數(shù)組來存儲結點的信息,本質上都是一樣的

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;
    }
}

2.插入字符串

    public void insert(String word) {
        Trie trie = this;//獲得根結點
        for (char c : word.toCharArray()) {
            if (trie.next.get(c) == null) {//當前結點不存在
                trie.next.put(c, new Trie());//創(chuàng)建當前結點
            }
            trie = trie.next.get(c);//得到字符c的結點,繼續(xù)向下遍歷
        }
        trie.isEnd = true;
    }

3.查找字符串

    public boolean search(String word) {
        Trie trie = this;//獲得根結點
        for (char c : word.toCharArray()) {
            if (trie.next.get(c) == null) {//當前結點不存在
                return false;
            }
            trie = trie.next.get(c);//得到字符c的結點,繼續(xù)向下遍歷
        }
        return trie.isEnd;
    }

4.查找前綴

    public boolean startsWith(String prefix) {
        Trie trie = this;//獲得根結點
        for (char c : prefix.toCharArray()) {
            if (trie.next.get(c) == null) {//當前結點不存在
                return false;
            }
            trie = trie.next.get(c);//得到字符c的結點,繼續(xù)向下遍歷
        }
        return true;
    }

接下來是力扣上關于前綴樹的一些題目

三.詞典中最長的單詞

1.題目描述

給出一個字符串數(shù)組words 組成的一本英語詞典。返回words 中最長的一個單詞，該單詞是由words詞典中其他單詞逐步添加一個字母組成。

若其中有多個可行的答案，則返回答案中字典序最小的單詞。若無答案，則返回空字符串。

力扣:力扣

2.問題分析

這是一道典型的前綴樹的問題,但是這一題有一些特殊的要求,返回的答案是:

1.最長的單詞

2.這個單詞由其他單詞逐步構成

3.長度相同返回字典序小的

因此我們需要對前綴樹的相關代碼進行修改,把字符串一一插入的代碼還是不改變的,主要修改的是查找的代碼,應該在 trie.next.get(c) == null在增加一個判斷為false的條件,就是每一個結點都應該有一個標志true,表示每個節(jié)點都存在一個單詞,最終一步步構成最長的單詞(葉子結點的單詞)

3.代碼實現(xià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;//獲得根結點
        for (char c : word.toCharArray()) {
            if (trie.next.get(c) == null) {//當前結點不存在
                trie.next.put(c, new Trie());//創(chuàng)建當前結點
            }
            trie = trie.next.get(c);//得到字符c的結點,繼續(xù)向下遍歷
        }
        trie.isEnd = true;
    }
    public boolean search(String word) {
        Trie trie = this;//獲得根結點
        for (char c : word.toCharArray()) {
            if (trie.next.get(c) == null || !trie.next.get(c).isEnd) {//當前結點不存在
                return false;
            }
            trie = trie.next.get(c);//得到字符c的結點,繼續(xù)向下遍歷
        }
        return trie.isEnd;
    }
}

到此這篇關于Java實現(xiàn)前綴樹詳解的文章就介紹到這了,更多相關Java前綴樹內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: