定義

前綴樹是N叉樹的一種特殊形式。通常來(lái)說(shuō)，一個(gè)前綴樹是用來(lái)存儲(chǔ)字符串的。前綴樹的每一個(gè)節(jié)點(diǎn)代表一個(gè)字符串（前綴）。每一個(gè)節(jié)點(diǎn)會(huì)有多個(gè)子節(jié)點(diǎn)，通往不同子節(jié)點(diǎn)的路徑上有著不同的字符。子節(jié)點(diǎn)代表的字符串是由節(jié)點(diǎn)本身的原始字符串，以及通往該子節(jié)點(diǎn)路徑上所有的字符組成的。

下面是前綴樹的一個(gè)例子：

在上圖示例中，我們?cè)诠?jié)點(diǎn)中標(biāo)記的值是該節(jié)點(diǎn)對(duì)應(yīng)表示的字符串。例如，我們從根節(jié)點(diǎn)開(kāi)始，選擇第二條路徑 ‘b’，然后選擇它的第一個(gè)子節(jié)點(diǎn) ‘a’，接下來(lái)繼續(xù)選擇子節(jié)點(diǎn) ‘d’，我們最終會(huì)到達(dá)葉節(jié)點(diǎn) “bad”。節(jié)點(diǎn)的值是由從根節(jié)點(diǎn)開(kāi)始，與其經(jīng)過(guò)的路徑中的字符按順序形成的。

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

前綴樹的一個(gè)重要的特性是，節(jié)點(diǎn)所有的后代都與該節(jié)點(diǎn)相關(guān)的字符串有著共同的前綴。這就是前綴樹名稱的由來(lái)。

我們?cè)賮?lái)看這個(gè)例子。例如，以節(jié)點(diǎn) “b” 為根的子樹中的節(jié)點(diǎn)表示的字符串，都具有共同的前綴 “b”。反之亦然，具有公共前綴 “b” 的字符串，全部位于以 “b” 為根的子樹中，并且具有不同前綴的字符串來(lái)自不同的分支。

前綴樹有著廣泛的應(yīng)用，例如自動(dòng)補(bǔ)全，拼寫檢查等等。我們將在后面的章節(jié)中介紹實(shí)際應(yīng)用場(chǎng)景。

問(wèn)題描述

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

示例:

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

說(shuō)明:

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

實(shí)現(xiàn)思路：

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

同時(shí)要實(shí)現(xiàn)搜索詞和搜索詞前綴?？紤]加入布爾標(biāo)識(shí)是否是一個(gè)詞。但插入詞的時(shí)候，到詞的最后一個(gè)字母時(shí)，將該節(jié)點(diǎn)布爾設(shè)為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);
 */

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

最新評(píng)論