未分類

Group Anagrams

Go, HashTable, LeetCode, String

Group Anagrams

Given an array of strings, group anagrams together.

For example:

Given: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
Return:

1
2
3
4
5
[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:

All inputs will be in lower-case.

提示 解題應用
HashTable HashMap
String 規律觀查

Default:

1
2
3
func groupAnagrams(strs []string) [][]string {
}

解答思路:

一開始的做法是每取出一個字串就遍歷一次計算該字串是由哪些字母且又有多少個所組成，並將此記錄存成hashmap放入陣列之中，之後的字串再找出由哪些字母、數量組成的記錄時逐一與陣列中所存的紀錄做比較，如果相同就放到與紀錄陣列位置相同的結果陣列之中，如果不同則將此新紀錄放入紀錄陣列之中，並存入結果陣列的新位置，但是這樣的做法雖然最後可以通過測資，但是拿到的新紀錄逐一與陣列中所存的紀錄做比較花費過多的時間，所以參考了其它比較好的做法是每取出一個字串就將其排序，雖然排序比起之前只遍歷一遍算由哪些字母、數量組成的記錄還來的花時間，但是只要將其排序後的字串存入hashmap的key中，而value則是一陣列用來儲存相同的結果，之後的排序字串要在hashmap中查找是否存在就只要O(1)的時間，最後一樣存在就將原字串放入hashmap對應的陣列之中，否則就以該排序的字串在hashmap中新增一個對應的陣列。

程式碼解說:

如先前所說，最佳的解法就是將字串排序完再利用一hashmap做分類儲存，在一開始就初始化一個hashamp，其中key值為排序後的字串，而value則是陣列用來儲存對應的原字串，接下來就是利用一迴圈將字串陣列的每個字串一一取出，而要將單一字串做排序就先將其再拆成字串陣(每個元素僅一個字母)，待排序完成後再合併回字串，接下來在hashmap中檢查排序字串是否存在，不過就這邊的程式碼來說，如果存在取出的對應陣列就不為空，而如果不存在則取出的是為空陣列，但是最後都是一律將原字串塞入該陣列之中並取代原陣列的位置，所以這邊就沒有在檢查排序字串是否於hashmap之中了，最後待分類全數結束後，剩下的就是將每個排序字串對應的陣列一一取出，合併成一個二元陣列後便回傳結果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var s []string
var sortStr string
var result [][]string
groups := make(map[string][]string)
for _, str := range strs {
	s = strings.Split(str, "")
	sort.Strings(s)
	sortStr = strings.Join(s, "")
	group, _ := groups[sortStr]
	group = append(group, str)
	groups[sortStr] = group
}
for _, group := range groups {
	result = append(result, group)
}
return result

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func groupAnagrams(strs []string) [][]string {
	var s []string
	var sortStr string
	var result [][]string
	groups := make(map[string][]string)
	for _, str := range strs {
		s = strings.Split(str, "")
		sort.Strings(s)
		sortStr = strings.Join(s, "")
		group, _ := groups[sortStr]
		group = append(group, str)
		groups[sortStr] = group
	}
	for _, group := range groups {
		result = append(result, group)
	}
	return result
}

總結:

給一陣列字串要將由相同字母、數量組成的字串放入同一陣列之中，最後回傳一個二元陣列的結果，其較佳的做法是每取出一個字串就將其排序，接著只要將其排序後的字串存入hashmap的key中，而value則是一陣列用來儲存相同的結果，之後的排序字串要在hashmap中查找是否存在，如果存在就將原字串放入hashmap對應的陣列之中，否則就以該排序的字串在hashmap中新增一個對應的陣列。

分享到