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