搜尋
首頁Javajava教程Java怎麼實作前綴樹

Java怎麼實作前綴樹

May 13, 2023 pm 02:43 PM
java

一.前綴樹

1.什麼是前綴樹

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

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

2.前綴樹的範例

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

  • 根結點不保存字元

  • 前綴樹是一顆多叉樹

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

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

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

Java怎麼實作前綴樹

二.前綴樹的實現

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

1.前綴樹的資料結構

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

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());//创建当前结点
            }
            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<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());//创建当前结点
            }
            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中文網其他相關文章!

陳述
本文轉載於:亿速云。如有侵權,請聯絡admin@php.cn刪除
Java開發的哪些方面取決於平台?Java開發的哪些方面取決於平台?Apr 26, 2025 am 12:19 AM

JavadevelovermentIrelyPlatForm-DeTueTososeVeralFactors.1)JVMVariationsAffectPerformanceNandBehaviorAcroSsdifferentos.2)Nativelibrariesviajnijniiniininiinniinindrododerplatefform.3)

在不同平台上運行Java代碼時是否存在性能差異?為什麼?在不同平台上運行Java代碼時是否存在性能差異?為什麼?Apr 26, 2025 am 12:15 AM

Java代碼在不同平台上運行時會有性能差異。 1)JVM的實現和優化策略不同,如OracleJDK和OpenJDK。 2)操作系統的特性,如內存管理和線程調度,也會影響性能。 3)可以通過選擇合適的JVM、調整JVM參數和代碼優化來提升性能。

Java平台獨立性有什麼局限性?Java平台獨立性有什麼局限性?Apr 26, 2025 am 12:10 AM

Java'splatFormentenceHaslimitations不包括PerformanceOverhead,versionCompatibilityIsissues,挑戰WithnativelibraryIntegration,Platform-SpecificFeatures,andjvminstallation/jvminstallation/jvmintenance/jeartenance.therefactorscomplicatorscomplicatethe“ writeOnce”

解釋平台獨立性和跨平台發展之間的差異。解釋平台獨立性和跨平台發展之間的差異。Apr 26, 2025 am 12:08 AM

PlatformIndependendecealLowsProgramStormonanyPlograwsStormanyPlatFormWithOutModification,而LileCross-PlatFormDevelopmentRequiredquiresMomePlatform-specificAdjustments.platFormIndependence,EneblesuniveByjava,EnablesuniversUniversAleversalexecutionbutmayCotutionButMayComproMisePerformance.cross.cross.cross-platformd

即時(JIT)彙編如何影響Java的性能和平台獨立性?即時(JIT)彙編如何影響Java的性能和平台獨立性?Apr 26, 2025 am 12:02 AM

JITcompilationinJavaenhancesperformancewhilemaintainingplatformindependence.1)Itdynamicallytranslatesbytecodeintonativemachinecodeatruntime,optimizingfrequentlyusedcode.2)TheJVMremainsplatform-independent,allowingthesameJavaapplicationtorunondifferen

為什麼Java是開發跨平台桌面應用程序的流行選擇?為什麼Java是開發跨平台桌面應用程序的流行選擇?Apr 25, 2025 am 12:23 AM

javaispopularforcross-platformdesktopapplicationsduetoits“ writeonce,runany where”哲學。 1)itusesbytiesebyTecodeThatrunsonAnyJvm-備用Platform.2)librarieslikeslikeslikeswingingandjavafxhelpcreatenative-lookingenative-lookinguisis.3)

討論可能需要在Java中編寫平台特定代碼的情況。討論可能需要在Java中編寫平台特定代碼的情況。Apr 25, 2025 am 12:22 AM

在Java中編寫平台特定代碼的原因包括訪問特定操作系統功能、與特定硬件交互和優化性能。 1)使用JNA或JNI訪問Windows註冊表;2)通過JNI與Linux特定硬件驅動程序交互;3)通過JNI使用Metal優化macOS上的遊戲性能。儘管如此,編寫平台特定代碼會影響代碼的可移植性、增加複雜性、可能帶來性能開銷和安全風險。

與平台獨立性相關的Java開發的未來趨勢是什麼?與平台獨立性相關的Java開發的未來趨勢是什麼?Apr 25, 2025 am 12:12 AM

Java將通過雲原生應用、多平台部署和跨語言互操作進一步提昇平台獨立性。 1)雲原生應用將使用GraalVM和Quarkus提升啟動速度。 2)Java將擴展到嵌入式設備、移動設備和量子計算機。 3)通過GraalVM,Java將與Python、JavaScript等語言無縫集成,增強跨語言互操作性。

See all articles

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱工具

SublimeText3 Linux新版

SublimeText3 Linux新版

SublimeText3 Linux最新版

MinGW - Minimalist GNU for Windows

MinGW - Minimalist GNU for Windows

這個專案正在遷移到osdn.net/projects/mingw的過程中,你可以繼續在那裡關注我們。 MinGW:GNU編譯器集合(GCC)的本機Windows移植版本,可自由分發的導入函式庫和用於建置本機Windows應用程式的頭檔;包括對MSVC執行時間的擴展,以支援C99功能。 MinGW的所有軟體都可以在64位元Windows平台上運作。

Atom編輯器mac版下載

Atom編輯器mac版下載

最受歡迎的的開源編輯器

mPDF

mPDF

mPDF是一個PHP庫,可以從UTF-8編碼的HTML產生PDF檔案。原作者Ian Back編寫mPDF以從他的網站上「即時」輸出PDF文件,並處理不同的語言。與原始腳本如HTML2FPDF相比,它的速度較慢,並且在使用Unicode字體時產生的檔案較大,但支援CSS樣式等,並進行了大量增強。支援幾乎所有語言,包括RTL(阿拉伯語和希伯來語)和CJK(中日韓)。支援嵌套的區塊級元素(如P、DIV),

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)