亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

Java實(shí)現(xiàn)前綴樹(shù)詳解

 更新時(shí)間:2023年04月27日 09:25:58   作者:允歆辰丶  
Java實(shí)現(xiàn)前綴樹(shù)(Trie樹(shù))是一種樹(shù)形數(shù)據(jù)結(jié)構(gòu),用于字符串的存儲(chǔ)和查找,適用于大量字符串的快速匹配。通過(guò)將字符串拆分為字符序列,依次構(gòu)建樹(shù)形結(jié)構(gòu),將每個(gè)字符串的字符依次存儲(chǔ)在樹(shù)的節(jié)點(diǎn)上,實(shí)現(xiàn)高效的字符串匹配

一.前綴樹(shù)

1.什么是前綴樹(shù)

字典樹(shù)(Trie樹(shù))是一種樹(shù)形數(shù)據(jù)結(jié)構(gòu),常用于字符串的存儲(chǔ)和查找。字典樹(shù)的核心思想是利用字符串之間的公共前綴來(lái)節(jié)省存儲(chǔ)空間和提高查詢效率。它是一棵多叉樹(shù),每個(gè)節(jié)點(diǎn)代表一個(gè)字符串的前綴,從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑組成一個(gè)字符串。

字典樹(shù)的根節(jié)點(diǎn)不包含字符,每個(gè)子節(jié)點(diǎn)代表一個(gè)字符,從根節(jié)點(diǎn)到任意一個(gè)節(jié)點(diǎn)所經(jīng)過(guò)的路徑上的字符連接起來(lái)即為該節(jié)點(diǎn)所代表的字符串。每個(gè)節(jié)點(diǎn)可以存儲(chǔ)一個(gè)或多個(gè)字符串,通常使用一個(gè)標(biāo)志來(lái)標(biāo)記一個(gè)節(jié)點(diǎn)代表的字符串是否存在。當(dāng)需要在一組字符串中查找某個(gè)字符串時(shí),可以利用字典樹(shù)來(lái)實(shí)現(xiàn)高效的查找操作。

2.前綴樹(shù)的舉例

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

  • 根結(jié)點(diǎn)不保存字符
  • 前綴樹(shù)是一顆多叉樹(shù)
  • 前綴樹(shù)的每個(gè)節(jié)點(diǎn)保存一個(gè)字符
  • 具有相同前綴的字符串保存在同一條路徑上
  • 字符串的尾處相應(yīng)的在前綴樹(shù)上也有結(jié)束的標(biāo)志

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

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

1.前綴樹(shù)的數(shù)據(jù)結(jié)構(gòu)

在寫(xiě)代碼的時(shí)候,我偏向于用哈希表來(lái)存儲(chǔ)結(jié)點(diǎn)的信息,有的也可以用數(shù)組來(lái)存儲(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;
    }
}

2.插入字符串

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

3.查找字符串

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

4.查找前綴

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

接下來(lái)是力扣上關(guān)于前綴樹(shù)的一些題目

三.詞典中最長(zhǎng)的單詞

1.題目描述

給出一個(gè)字符串?dāng)?shù)組words 組成的一本英語(yǔ)詞典。返回words 中最長(zhǎng)的一個(gè)單詞,該單詞是由words詞典中其他單詞逐步添加一個(gè)字母組成。

若其中有多個(gè)可行的答案,則返回答案中字典序最小的單詞。若無(wú)答案,則返回空字符串。

力扣:力扣

2.問(wèn)題分析

這是一道典型的前綴樹(shù)的問(wèn)題,但是這一題有一些特殊的要求,返回的答案是:

1.最長(zhǎng)的單詞

2.這個(gè)單詞由其他單詞逐步構(gòu)成

3.長(zhǎng)度相同返回字典序小的

因此我們需要對(duì)前綴樹(shù)的相關(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)成最長(zhǎng)的單詞(葉子結(jié)點(diǎn)的單詞)

3.代碼實(shí)現(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;//獲得根結(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;
    }
}

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

相關(guān)文章

  • 關(guān)于SpringBoot大文件RestTemplate下載解決方案

    關(guān)于SpringBoot大文件RestTemplate下載解決方案

    這篇文章主要介紹了SpringBoot大文件RestTemplate下載解決方案,最近結(jié)合網(wǎng)上案例及自己總結(jié),寫(xiě)了一個(gè)分片下載tuling/fileServer項(xiàng)目,需要的朋友可以參考下
    2021-10-10
  • MapReduce核心思想圖文詳解

    MapReduce核心思想圖文詳解

    今天小編就為大家分享一篇關(guān)于MapReduce核心思想圖文詳解,小編覺(jué)得內(nèi)容挺不錯(cuò)的,現(xiàn)在分享給大家,具有很好的參考價(jià)值,需要的朋友一起跟隨小編來(lái)看看吧
    2019-01-01
  • 解決springboot+activemq啟動(dòng)報(bào)注解錯(cuò)誤的問(wèn)題

    解決springboot+activemq啟動(dòng)報(bào)注解錯(cuò)誤的問(wèn)題

    這篇文章主要介紹了解決springboot+activemq啟動(dòng)報(bào)注解錯(cuò)誤的問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2021-07-07
  • 詳解Java的編譯執(zhí)行與解釋執(zhí)行

    詳解Java的編譯執(zhí)行與解釋執(zhí)行

    這篇文章主要介紹了Java的編譯執(zhí)行與解釋執(zhí)行,對(duì)編譯和解釋感興趣的同學(xué),可以參考下
    2021-04-04
  • 解決OkHttp接收gzip壓縮數(shù)據(jù)返回亂碼問(wèn)題

    解決OkHttp接收gzip壓縮數(shù)據(jù)返回亂碼問(wèn)題

    這篇文章主要介紹了解決OkHttp接收gzip壓縮數(shù)據(jù)返回亂碼問(wèn)題,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2022-06-06
  • Java中ConcurrentHashMap是如何實(shí)現(xiàn)線程安全

    Java中ConcurrentHashMap是如何實(shí)現(xiàn)線程安全

    ConcurrentHashMap是一個(gè)哈希表,支持檢索的全并發(fā)和更新的高預(yù)期并發(fā)。本文主要介紹了Java中ConcurrentHashMap是如何實(shí)現(xiàn)線程安全,感興趣的可以了解一下
    2021-11-11
  • MyBatis Plus關(guān)閉SQL日志打印的方法

    MyBatis Plus關(guān)閉SQL日志打印的方法

    這篇文章主要介紹了MyBatis-Plus如何關(guān)閉SQL日志打印,文中通過(guò)圖文結(jié)合講解的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2024-02-02
  • Spring Boot + Mybatis多數(shù)據(jù)源和動(dòng)態(tài)數(shù)據(jù)源配置方法

    Spring Boot + Mybatis多數(shù)據(jù)源和動(dòng)態(tài)數(shù)據(jù)源配置方法

    最近做項(xiàng)目遇到這樣的應(yīng)用場(chǎng)景,項(xiàng)目需要同時(shí)連接兩個(gè)不同的數(shù)據(jù)庫(kù)A, B,并且它們都為主從架構(gòu),一臺(tái)寫(xiě)庫(kù),多臺(tái)讀庫(kù)。下面小編給大家?guī)?lái)了Spring Boot + Mybatis多數(shù)據(jù)源和動(dòng)態(tài)數(shù)據(jù)源配置方法,需要的朋友參考下吧
    2018-01-01
  • 詳解Spring?@Lazy注解為什么能破解死循環(huán)

    詳解Spring?@Lazy注解為什么能破解死循環(huán)

    這篇文章主要來(lái)和大家探討一下Spring中的@Lazy注解為什么能破解死循環(huán),文中的示例代碼講解詳細(xì),具有一定的參考價(jià)值,需要的可以了解一下
    2023-07-07
  • JAVA中string數(shù)據(jù)類型轉(zhuǎn)換詳解

    JAVA中string數(shù)據(jù)類型轉(zhuǎn)換詳解

    在JAVA中string是final類,提供字符串不可以修改,string類型在項(xiàng)目中經(jīng)常使用,下面給大家介紹了string七種數(shù)據(jù)類型轉(zhuǎn)換,需要的朋友可以參考下
    2015-07-07

最新評(píng)論