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ù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: