Java怎麼實作前綴樹

一.前綴樹

1.什麼是前綴樹

字典樹（Trie樹）是一種樹狀資料結構，常用於字串的儲存與尋找。字典樹的核心思想是利用字串之間的公共前綴來節省儲存空間和提高查詢效率。它是一棵多叉樹，每個節點代表一個字串的前綴，從根節點到葉子節點的路徑組成一個字串。

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

2.前綴樹的範例

例如對字串陣列{"goog","google","bai","baidu","a"}建立前綴樹,此時我們可以很清楚的看到前綴樹的一些特徵:

• 根結點不保存字元

• 前綴樹是一顆多叉樹

• 前綴樹的每個節點保存一個字元

• #具有相同前綴的字串保存在同一路徑上

• 字串的尾處對應的在前綴樹上也有結束的標誌

二.前綴樹的實現

力扣上的208題就是實現前綴樹:力扣

1.前綴樹的資料結構

在寫程式碼的時候,我偏向於用哈希表來儲存結點的資訊,有的也可以用數組來儲存結點的資訊,本質上都是一樣的

public class Trie {
    Map 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());//创建当前结点
            }
            trie = trie.next.get(c);//得到字符c的结点,继续向下遍历
        }
        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的结点,继续向下遍历
        }
        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的结点,继续向下遍历
        }
        return true;
    }

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

三.字典中最長的單字

#1.題目描述

給出一個字串陣列words 組成的一本英文字典。傳回words 中最長的一個單字，該單字由words字典中其他單字逐步添加一個字母組成。

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

力扣:力扣

2.問題分析

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

1.最長的單字

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

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

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

#3.程式碼實作

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 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());//创建当前结点
            }
            trie = trie.next.get(c);//得到字符c的结点,继续向下遍历
        }
        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的结点,继续向下遍历
        }
        return trie.isEnd;
    }
}

以上是Java怎麼實作前綴樹的詳細內容。更多資訊請關注PHP中文網其他相關文章！