搜尋
首頁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结构化数据处理开源库SPL带你搞懂Java结构化数据处理开源库SPLMay 24, 2022 pm 01:34 PM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于结构化数据处理开源库SPL的相关问题,下面就一起来看一下java下理想的结构化数据处理类库,希望对大家有帮助。

Java集合框架之PriorityQueue优先级队列Java集合框架之PriorityQueue优先级队列Jun 09, 2022 am 11:47 AM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于PriorityQueue优先级队列的相关知识,Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列,PriorityQueue是线程不安全的,PriorityBlockingQueue是线程安全的,下面一起来看一下,希望对大家有帮助。

完全掌握Java锁(图文解析)完全掌握Java锁(图文解析)Jun 14, 2022 am 11:47 AM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于java锁的相关问题,包括了独占锁、悲观锁、乐观锁、共享锁等等内容,下面一起来看一下,希望对大家有帮助。

一起聊聊Java多线程之线程安全问题一起聊聊Java多线程之线程安全问题Apr 21, 2022 pm 06:17 PM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于多线程的相关问题,包括了线程安装、线程加锁与线程不安全的原因、线程安全的标准类等等内容,希望对大家有帮助。

详细解析Java的this和super关键字详细解析Java的this和super关键字Apr 30, 2022 am 09:00 AM

本篇文章给大家带来了关于Java的相关知识,其中主要介绍了关于关键字中this和super的相关问题,以及他们的一些区别,下面一起来看一下,希望对大家有帮助。

Java基础归纳之枚举Java基础归纳之枚举May 26, 2022 am 11:50 AM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于枚举的相关问题,包括了枚举的基本操作、集合类对枚举的支持等等内容,下面一起来看一下,希望对大家有帮助。

java中封装是什么java中封装是什么May 16, 2019 pm 06:08 PM

封装是一种信息隐藏技术,是指一种将抽象性函式接口的实现细节部分包装、隐藏起来的方法;封装可以被认为是一个保护屏障,防止指定类的代码和数据被外部类定义的代码随机访问。封装可以通过关键字private,protected和public实现。

归纳整理JAVA装饰器模式(实例详解)归纳整理JAVA装饰器模式(实例详解)May 05, 2022 pm 06:48 PM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于设计模式的相关问题,主要将装饰器模式的相关内容,指在不改变现有对象结构的情况下,动态地给该对象增加一些职责的模式,希望对大家有帮助。

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脫衣器

AI Hentai Generator

AI Hentai Generator

免費產生 AI 無盡。

熱門文章

R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
2 週前By尊渡假赌尊渡假赌尊渡假赌
倉庫:如何復興隊友
1 個月前By尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒險:如何獲得巨型種子
4 週前By尊渡假赌尊渡假赌尊渡假赌

熱工具

MantisBT

MantisBT

Mantis是一個易於部署的基於Web的缺陷追蹤工具,用於幫助產品缺陷追蹤。它需要PHP、MySQL和一個Web伺服器。請查看我們的演示和託管服務。

VSCode Windows 64位元 下載

VSCode Windows 64位元 下載

微軟推出的免費、功能強大的一款IDE編輯器

Dreamweaver Mac版

Dreamweaver Mac版

視覺化網頁開發工具

SublimeText3 英文版

SublimeText3 英文版

推薦:為Win版本,支援程式碼提示!

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器