未分類

Add and Search Word - Data structure design

Backtracking, Design, Go, LeetCode, Trie

Add and Search Word - Data structure design

Design a data structure that supports the following two operations:

1
2
void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

For example:

1
2
3
4
5
6
7
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Note:

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

提示 解題應用
Backtracking Recursive
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
type WordDictionary struct {
    
}
/** Initialize your data structure here. */
func Constructor() WordDictionary {
    
}
/** Adds a word into the data structure. */
func (this *WordDictionary) AddWord(word string)  {
    
}
/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
func (this *WordDictionary) Search(word string) bool {
    
}
/**
 * Your WordDictionary object will be instantiated and called as such:
 * obj := Constructor();
 * obj.AddWord(word);
 * param_2 := obj.Search(word);
 */

解答思路:

建議可以先參考先前Implement Trie (Prefix Tree)的解法，解說較為詳細，基本上概念完全一樣，只是這次在搜尋Trie的部分多了一個可以用”.”來取代任何值，這意味著當碰上”.”的時候要嘗試所有的可能，因此需要將原本的搜尋函數修改成以遞回的方式來做搜尋，當碰上”.”的時候就需要遞回以嘗試所有的可能，否則就只要像之前一樣直接繼續往下做檢查即可，至於搜尋函數以外的function則全數與先前完全一樣就不會有什麼大問題。

程式碼解說:

這邊只解說與先前題目程式碼的相異之處，最主要就是將搜尋函數修改成以遞回的方式來嘗試所有的可能，所以一開始便將Trie的節點與要搜尋的目標帶入遞回函數之中，而如果沒有碰上”.”的情況下，基本上就與先前一樣利用迴圈取出字元的rune值-97當作index，如果中間字元不存在或者已經到最後一個字母卻發現其不為單字，便一律回傳false，如果單字取出檢查都沒有問題最後才回傳true

1
2
3
4
5
6
7
8
9
10
11
12
13
func (this *WordDictionary) Search(word string) bool {
	return Match(this, word)
}
func Match(this *WordDictionary, 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
}

萬一取出的字元是”.”，此時就需要另外做處理，因為”.”可以用來取代任何值，一開始便遍歷陣列所有不為nil的節點，如果該”.”所在位置是單字的最後一個字元，此時就只要檢查該節點是否標示為單字，而如果不是最後一個字元則以該節點作為”.”與單字剩餘的字元帶入遞回函數再次判斷此單字是否存在，最後如果exist為true表示至少有一個(或更多)符合搜尋的條件

1
2
3
4
5
6
7
8
9
10
11
12
13
var exist bool
if string(v) == "." {
	for _, n := range this.Node {
		if n != nil {
			if i+1 == len(word) {
				exist = exist || n.IsWord
			} else {
				exist = exist || Match(n, word[i+1:])
			}
		}
	}
	return exist
}

完整程式碼:

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
37
38
39
40
41
type WordDictionary struct {
	IsWord bool
	Node   [26]*WordDictionary
}
func Constructor() WordDictionary {
	return WordDictionary{}
}
func (this *WordDictionary) AddWord(word string) {
	for _, v := range word {
		if this.Node[v-97] == nil {
			this.Node[v-97] = &WordDictionary{}
		}
		this = this.Node[v-97]
	}
	this.IsWord = true
}
func (this *WordDictionary) Search(word string) bool {
	return Match(this, word)
}
func Match(this *WordDictionary, word string) bool {
	var exist bool
	for i, v := range word {
		if string(v) == "." {
			for _, n := range this.Node {
				if n != nil {
					if i+1 == len(word) {
						exist = exist || n.IsWord
					} else {
						exist = exist || Match(n, word[i+1:])
					}
				}
			}
			return exist
		}
		if (this.Node[v-97] == nil) || (i+1 == len(word) && !this.Node[v-97].IsWord) {
			return false
		}
		this = this.Node[v-97]
	}
	return true
}

總結:

建議可以先參考先前Implement Trie (Prefix Tree)的解法，解說較為詳細，基本上概念完全一樣，只是這次在搜尋Trie的部分多了一個可以用”.”來取代任何值，這意味著當碰上”.”的時候，需要將原本的搜尋函數修改成以遞回的方式來嘗試所有的可能，否則就只要像之前一樣直接繼續往下做檢查即可。

分享到