欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Golang實現(xiàn)Trie(前綴樹)的示例

 更新時間:2023年01月03日 11:22:21   作者:terrygmx  
本文主要介紹了Golang實現(xiàn)Trie(前綴樹)的示例,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧

定義

前綴樹是N叉樹的一種特殊形式。通常來說,一個前綴樹是用來存儲字符串的。前綴樹的每一個節(jié)點代表一個字符串(前綴)。每一個節(jié)點會有多個子節(jié)點,通往不同子節(jié)點的路徑上有著不同的字符。子節(jié)點代表的字符串是由節(jié)點本身的原始字符串,以及通往該子節(jié)點路徑上所有的字符組成的。

下面是前綴樹的一個例子:

在這里插入圖片描述

在上圖示例中,我們在節(jié)點中標記的值是該節(jié)點對應表示的字符串。例如,我們從根節(jié)點開始,選擇第二條路徑 ‘b’,然后選擇它的第一個子節(jié)點 ‘a’,接下來繼續(xù)選擇子節(jié)點 ‘d’,我們最終會到達葉節(jié)點 “bad”。節(jié)點的值是由從根節(jié)點開始,與其經過的路徑中的字符按順序形成的。

值得注意的是,根節(jié)點表示空字符串。

前綴樹的一個重要的特性是,節(jié)點所有的后代都與該節(jié)點相關的字符串有著共同的前綴。這就是前綴樹名稱的由來。

我們再來看這個例子。例如,以節(jié)點 “b” 為根的子樹中的節(jié)點表示的字符串,都具有共同的前綴 “b”。反之亦然,具有公共前綴 “b” 的字符串,全部位于以 “b” 為根的子樹中,并且具有不同前綴的字符串來自不同的分支。

前綴樹有著廣泛的應用,例如自動補全,拼寫檢查等等。我們將在后面的章節(jié)中介紹實際應用場景。

問題描述

實現(xiàn)一個 Trie (前綴樹),包含 insert, search, 和 startsWith 這三個操作。

示例:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // 返回 true
trie.search("app");     // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");   
trie.search("app");     // 返回 true

說明:

你可以假設所有的輸入都是由小寫字母 a-z 構成的。
保證所有輸入均為非空字符串。

實現(xiàn)思路:

由于所有輸入都是小寫字母構成,可以用桶的方式實現(xiàn),雖然有空間浪費,但是速度最快。

同時要實現(xiàn)搜索詞和搜索詞前綴。考慮加入布爾標識是否是一個詞。但插入詞的時候,到詞的最后一個字母時,將該節(jié)點布爾設為true 代碼:

type Trie struct {
	isWord   bool
	children [26]*Trie
}

/** Initialize your data structure here. */
func Constructor() Trie {
	return Trie{}
}

/** Inserts a word into the trie. */
func (this *Trie) Insert(word string) {
	cur := this
	for i, c := range word {
		n := c - 'a'

		if cur.children[n] == nil {
			cur.children[n] = &Trie{}

		}
		cur = cur.children[n]
		if i == len(word)-1 {
			cur.isWord = true
		}

	}
}

/** Returns if the word is in the trie. */
func (this *Trie) Search(word string) bool {
	cur := this
	for _, c := range word {
		n := c - 'a'
		if cur.children[n] == nil {
			return false
		}
		cur = cur.children[n]
	}
	return cur.isWord
}

/** Returns if there is any word in the trie that starts with the given prefix. */
func (this *Trie) StartsWith(prefix string) bool {
	cur := this
	for _, c := range prefix {
		n := c - 'a'
		if cur.children[n] == nil {
			return false
		}
		cur = cur.children[n]
	}
	return true
}

/**
 * Your Trie object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Insert(word);
 * param_2 := obj.Search(word);
 * param_3 := obj.StartsWith(prefix);
 */

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

相關文章

  • Go+Redis實現(xiàn)延遲隊列實操

    Go+Redis實現(xiàn)延遲隊列實操

    這篇文章主要介紹了Go+Redis實現(xiàn)延遲隊列實操,延遲隊列是一種非常使用的數據結構,我們經常有需要延遲推送處理消息的場景,比如延遲60秒發(fā)送短信,延遲30分鐘關閉訂單,消息消費失敗延遲重試等
    2022-09-09
  • golang下的viper包的簡單使用方式

    golang下的viper包的簡單使用方式

    這篇文章主要介紹了golang下的viper包的簡單使用方式,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2023-06-06
  • GO語言Context的作用及各種使用方法

    GO語言Context的作用及各種使用方法

    golang的Context包是專門用來處理多個goroutine之間與請求域的數據、取消信號、截止時間等相關操作,下面這篇文章主要給大家介紹了關于GO語言Context的作用及各種使用方法的相關資料,需要的朋友可以參考下
    2024-01-01
  • go cron定時任務的基本使用講解

    go cron定時任務的基本使用講解

    這篇文章主要為大家介紹了gocron定時任務的基本使用講解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
    2023-06-06
  • 淺析Go語言如何在select語句中實現(xiàn)優(yōu)先級

    淺析Go語言如何在select語句中實現(xiàn)優(yōu)先級

    這篇文章主要為大家詳細介紹了Go語言如何在select語句中實現(xiàn)優(yōu)先級,文中的示例代碼講解詳細,感興趣的小伙伴可以跟隨小編一起學習一下
    2024-03-03
  • Golang實現(xiàn)自定義recovery中間件

    Golang實現(xiàn)自定義recovery中間件

    在?Golang?的?Web?項目中,自定義?recovery?中間件是一種常見的做法,用于捕獲并處理應用程序的運行時錯誤,下面我們就來看看具體如何實現(xiàn)吧
    2023-09-09
  • golang連接mysql數據庫操作使用示例

    golang連接mysql數據庫操作使用示例

    這篇文章主要為大家介紹了golang連接mysql數據庫操作使用示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步早日升職加薪
    2022-04-04
  • Go語言中使用gorm小結

    Go語言中使用gorm小結

    這篇文章主要給大家介紹了Go語言中如何使用gorm,文中介紹的很詳細,有需要的朋友們可以參考借鑒,下面來一起看看吧。
    2016-12-12
  • Go語言入門13之runtime包案例講解

    Go語言入門13之runtime包案例講解

    這篇文章主要介紹了Go語言入門runtime包相關知識,本文給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2023-05-05
  • 一文帶你了解Go語言中的函數

    一文帶你了解Go語言中的函數

    函數是編程中不可或缺的組成部分,在本文中,我們將詳細介紹Go語言中函數的概念和使用方法,包括函數的定義、參數和返回值等,需要的可以參考一下
    2023-06-06

最新評論