未分類

Implement Trie (Prefix Tree)

Design, Go, LeetCode, Trie

Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.

Note:

You may assume that all inputs are consist of lowercase letters a-z.

提示 解題應用
Trie Tree

Default:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
type Trie struct {
    
}
/** Initialize your data structure here. */
func Constructor() Trie {
    
}
/** Inserts a word into the trie. */
func (this *Trie) Insert(word string)  {
    
}
/** Returns if the word is in the trie. */
func (this *Trie) Search(word string) bool {
    
}
/** Returns if there is any word in the trie that starts with the given prefix. */
func (this *Trie) StartsWith(prefix string) bool {
    
}
/**
 * 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);
 */

解答思路:

這次要用Tree實作字典檔或稱前綴樹，大致如下圖所示:

圖片取自維基百科

相較於用hashmap的字典檔只有O(1)的時間複雜度，Trie最糟可能會到O(n)(n為字串長度)而且又會花費大量的空間，不過當有需要找字串間前綴的關連性才能發揮Trie的價值，至於要實作Trie只要注意到節點本身並不儲單一字元的值，而是一長度26(若字串只由a~z組成)陣列來各別放置下一節點的位置，如此一來就可以只透過位置的順序來知道該位置是哪個字母，此外在找下一個字母位置也就不必一個個遍歷，而是直接將字母當ascii減去97就會是對應陣列的index，接著再檢查該位置是否為nil就可以得知字母是否存在，最後節點還要標示到該位置時是否為單字，因為單字並非一定要到葉子節點，像是出現”in”及”inn”兩個字的情況便是如此。

程式碼解說:

一開始先初始化Trie節點的結構，其中標示到該位置時是否為單字之外，還有長度26(若字串只由a~z組成)陣列來各別放置下一節點的位置

1
2
3
4
5
6
7
type Trie struct {
	IsWord bool
	Node   [26]*Trie
}
func Constructor() Trie {
	return Trie{}
}

接著就是來實作將單字插入Trie的函數，利用迴圈從單字一一取出字元的rune值後-97當作index，並檢查陣列中該位置是否為nil，如果是就在該位置自行新增一個Trie的節點，否則就從該位置開始繼續往下遍歷，最後當到達單字的最後一個字母時，記得在該位置的節點要標示為單字

1
2
3
4
5
6
7
8
9
func (this *Trie) Insert(word string) {
	for _, v := range word {
		if this.Node[v-97] == nil {
			this.Node[v-97] = &Trie{}
		}
		this = this.Node[v-97]
	}
	this.IsWord = true
}

搜尋函數則也是利用迴圈取出字元的rune值-97當作index，如果中間字元不存在或者已經到最後一個字母卻發現其不為單字，便一律回傳false，如果單字取出檢查都沒有問題最後才回傳true

1
2
3
4
5
6
7
8
9
func (this *Trie) Search(word string) bool {
	for i, v := range word {
		if (this.Node[v-97] == nil) || (i+1 == len(word) && !this.Node[v-97].IsWord) {
			return false
		}
		this = this.Node[v-97]
	}
	return true
}

至於尋找是否有特定的前綴字串和搜尋函數非常相似，只是這次僅需確認前綴是否存在而非單字，所以就不需要檢查最後一個字母是否標示為單字

1
2
3
4
5
6
7
8
9
func (this *Trie) StartsWith(prefix string) bool {
	for _, v := range prefix {
		if this.Node[v-97] == nil {
			return false
		}
		this = this.Node[v-97]
	}
	return true
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
type Trie struct {
	IsWord bool
	Node   [26]*Trie
}
func Constructor() Trie {
	return Trie{}
}
func (this *Trie) Insert(word string) {
	for _, v := range word {
		if this.Node[v-97] == nil {
			this.Node[v-97] = &Trie{}
		}
		this = this.Node[v-97]
	}
	this.IsWord = true
}
func (this *Trie) Search(word string) bool {
	for i, v := range word {
		if (this.Node[v-97] == nil) || (i+1 == len(word) && !this.Node[v-97].IsWord) {
			return false
		}
		this = this.Node[v-97]
	}
	return true
}
func (this *Trie) StartsWith(prefix string) bool {
	for _, v := range prefix {
		if this.Node[v-97] == nil {
			return false
		}
		this = this.Node[v-97]
	}
	return true
}

總結:

要用Tree實作字典檔(前綴樹)，其節點本身並不儲單一字元的值，而是一長度26(若字串只由a~z組成)陣列來各別放置下一節點的位置，透過位置的順序來知道該位置的字母，而找下一個字母位置則是直接將字母當ascii減去97作為陣列的index，檢查該位置是否為nil就可以得知字母是否存在，最後節點還要標示到該位置時是否為單字，因為單字並非一定都到葉子節點。

分享到