[LeetCode] 49. Group Anagrams

轉自LeetCode

Given an array of strings, group anagrams together.

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],
Return:

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note: All inputs will be in lower-case.

<Solution>

首先，要了解什麼是 anagram

簡單說，就是一個字串，用同樣的字母再次重新排列

那這題是要將同個 anagram 的所有字串，都放在一起

因為 anagram 就是用樣字母重新排列

所以對於每個字串，都把它 sort 一次，這樣只要是同個 anagram，sort 之後就會一樣

因此就可以用來當作 hash map 的 key，藉此分群 (參考資料)

code 如下

c++

	class Solution {
	public:
	vector<vector<string>> groupAnagrams(vector<string>& strs) {
	unordered_map<string, vector<string>> hashMap;
	for(auto s: strs) {
	string tmpS = s;
	//> sort the tmpS and use it as key of hash map
	sort(tmpS.begin(), tmpS.end());
	hashMap[tmpS].push_back(s);
	}
	//> return ans
	vector<vector<string>> ans;
	for(auto e: hashMap) {
	ans.push_back(e.second);
	}
	return ans;
	}
	};

view raw groupAnagrams.cpp hosted with ❤ by GitHub

Kotlin

	class Solution {
	fun groupAnagrams(strs: Array<String>): List<List<String>> {
	val map = mutableMapOf<String,MutableList<String>>()
	var sortedString: String
	for(s in strs) {
	sortedString = s.toCharArray().sorted().joinToString("")
	if (map[sortedString] == null) {
	map[sortedString] = arrayListOf(s)
	} else {
	map[sortedString]!!.add(s)
	}
	}
	return map.map { it.value }
	}
	}

view raw group_anagrams.kt hosted with ❤ by GitHub

另外一種想法是，因為 anagram 都是用同樣的字母

可以用這些字母出現的次數來做一個 key，再用這個 key 來做 grouping

Kotlin

	class Solution {
	fun groupAnagrams(strs: Array<String>): List<List<String>> {
	val map = mutableMapOf<String,MutableList<String>>()
	for(s in strs) {
	val keyTable = IntArray(26) {0}
	for(c in s) {
	keyTable[c-'a'] += 1
	}
	val sb = StringBuilder()
	for(k in keyTable) {
	sb.append("#")
	sb.append(k)
	}
	val key = sb.toString()
	if (map[key] == null) {
	map[key] = arrayListOf(s)
	} else {
	map[key]!!.add(s)
	}
	}
	return map.map { it.value }
	}
	}

view raw group_anagrams.kt hosted with ❤ by GitHub