日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

Golang實現Trie(前綴樹)的示例_Golang

作者：terrygmx ? 更新時間： 2023-02-09 編程語言

定義

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

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

在這里插入圖片描述

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

值得注意的是，根節點表示空字符串。

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

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

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

問題描述

實現一個 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 構成的。
保證所有輸入均為非空字符串。

實現思路：

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

同時要實現搜索詞和搜索詞前綴。考慮加入布爾標識是否是一個詞。但插入詞的時候，到詞的最后一個字母時，將該節點布爾設為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);
 */

原文鏈接：https://blog.csdn.net/terrygmx/article/details/88921823

欄目分類
最近更新