49. Group Anagrams

LeetCode 49. Group Anagrams

Description

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: [[""]]

Constraints:

• 1 <= strs.length <= 104

• 0 <= strs[i].length <= 100

• strs[i] consists of lower-case English letters.

Tags

Hash Table, String

Solution

Two strings are anagrams if and only if their character counts (respective number of occurrences of each character) are the same.

We use a map to group anagrams, whose key type is [26]int for count characters of a word and value type is []string to collect words. For example, if 'a' occurred in a word, we get the element at position 0 of [26]int increased by 1. Finally, we append all values of the map to a 2D string array as the return value.

Complexity

• Time complexity: $O(n(k+26))$, n for the length of strs; k for the length of the longest word.

• Space complexity: $O(n(k+26))$

Code

func groupAnagrams(strs []string) [][]string {
	var ans [][]string
	m := map[[26]int][]string{}
	for _, s := range strs {
		var key [26]int
		for _, c := range s {
			key[c-'a']++
		}
		m[key] = append(m[key], s)
	}
	for _, strings := range m {
		ans = append(ans, strings)
	}
	return ans
}

Reference

1. 字母异位词分组