LeetCode 049 Group Anagrams

LeetCode

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: strs = [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”]
Output: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]

Example 2:

Input: strs = [“”]
Output: [[“”]]

Example 3:

Input: strs = [“a”]
Output: [[“a”]]

Constraints:

1 <= strs.length <= 10<sup>4</sup> 0 <= strs[i].length <= 100
* strs[i] consists of lowercase English letters.

题目大意：

对同字母不同序单词分组

算法思路：

N/A

注意事项：

1. list(id_to_words.values())要转成list

Python代码：

def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
	id_to_words = collections.defaultdict(list)
	for word in strs:
		id_to_words[self.get_id(word)].append(word)
	return list(id_to_words.values())  # remember to convert it to list

def get_id(self, word):
	char_to_freq = collections.Counter(word)
	res = ''
	for c in string.ascii_lowercase:
		if c in char_to_freq:
			res += c + str(char_to_freq[c])
	return res

算法分析：

时间复杂度为O(nm)，空间复杂度O(n+m). n是单词个数，m是单词长度