未分類

Word Pattern

Go, HashTable, LeetCode, Math

Word Pattern

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

For Examples:

1
2
3
4
pattern = "abba", str = "dog cat cat dog" should return true.
pattern = "abba", str = "dog cat cat fish" should return false.
pattern = "aaaa", str = "dog cat cat dog" should return false.
pattern = "abba", str = "dog dog dog dog" should return false.

Notes:

You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

提示 解題應用
HashTable HashMap

Default:

1
2
3
func wordPattern(pattern string, str string) bool {
}

解答思路:

這題沒有什麼大問題，基本上就是1個字母對上1個單字，而且關係為1對1的絕對關係，所以如果以hashmap來儲存的話可以以同一個來同時放key(字母)、value(單字)與key(單字)、value(字母)，或者是拆成兩個hashmap意思也一樣，總之一定要同時存放相反的key與value才能以空間來換取時間加快。

程式碼解說:

一開始先將所給予的單字組以單一空白一一切開，接著先判斷字母組的長度是否與要對照的單字組一樣長，不一通樣的話就直接回傳false來篩選例外的狀況

1
2
3
4
strSplit := strings.Split(str, " ")
if len(pattern) != len(strSplit) {
	return false
}

接著便能開始對照每個字組，如前述所提這邊我以兩個hashmap來儲存字母與單字分別為key與value的兩種狀況，接著就開始遍歷每個字組，不管是哪個hashmap，只要其中一個字組存在就檢查其key對應的value是否與儲存的相同，如果不同就回傳false，如果字組根本不在hashmap裡頭，就在後頭分別儲存至兩種hashmap(如果字組存在且值一樣會直接再覆蓋一次)，最後驗證完全部的字組後才回傳true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var word string
origin := make(map[rune]string)
reverse := make(map[string]rune)
for i, v := range pattern {
	word = strSplit[i]
	oValue, oOk := origin[v]
	rValue, rOk := reverse[word]
	if oOk && word != oValue {
		return false
	}
	if rOk && v != rValue {
		return false
	}
	origin[v] = word
	reverse[word] = v
}
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
func wordPattern(pattern string, str string) bool {
	strSplit := strings.Split(str, " ")
	if len(pattern) != len(strSplit) {
		return false
	}
	var word string
	origin := make(map[rune]string)
	reverse := make(map[string]rune)
	for i, v := range pattern {
		word = strSplit[i]
		oValue, oOk := origin[v]
		rValue, rOk := reverse[word]
		if oOk && word != oValue {
			return false
		}
		if rOk && v != rValue {
			return false
		}
		origin[v] = word
		reverse[word] = v
	}
	return true
}

總結:

如果有特定字母對照特定的單字，且為1對1的絕對關係的話，除用將字母對單字以key&value來存放之外，也別忘記儲存相反的狀況:單字對字母，至於要存放在同一個hashmap或拆成兩個則隨意。

分享到