Group Anagrams

Medium

The problem

Given a list of words, put the words that are anagrams of each other (same letters, rearranged) into the same group, and return all the groups. The groups can be in any order, and so can the words inside a group.

Example 1
Input: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
Output: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
"eat", "tea" and "ate" use the same letters; so do "tan" and "nat"; "bat" has no partner.
Example 2
Input: strs = ["a"]
Output: [["a"]]
A single word forms a group by itself.

Limits

1 ≤ strs.length ≤ 10,000
0 ≤ strs[i].length ≤ 100
Each word has only lowercase letters a to z

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

You need a label that is identical for all words that are anagrams of each other.

The idea

Build a key per word (its letters sorted, or its 26 letter counts) and append the word to a map from key to list.

Target: O(n·k) time with count keys (k = word length)

Go function shape

func groupAnagrams(strs []string) [][]string

Reference solution

Tested with go test. Try it yourself first, then compare.

// GroupAnagrams: words with the same letter counts share a key.
func GroupAnagrams(words []string) [][]string {
	groups := map[[26]int][]string{} // arrays are comparable, so they can be keys
	for _, w := range words {
		var key [26]int
		for i := 0; i < len(w); i++ {
			key[w[i]-'a']++
		}
		groups[key] = append(groups[key], w)
	}
	out := make([][]string, 0, len(groups))
	for _, g := range groups {
		out = append(out, g)
	}
	return out
}

Read the lesson: Arrays & Hash Map