Group Anagrams

Problem

Given an array of strings strs, group the anagrams together. The groups may be returned in any order.

What is an anagram? An anagram is a word formed by rearranging the letters of another word, using every letter exactly once. So "eat", "tea", and "ate" are all anagrams of one another — same letters, different order. Two words are anagrams if and only if they contain the same letters with the same counts.

Example

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

Go Solution

package main

import (
    "fmt"
    "sort"
)

func groupAnagrams(strs []string) [][]string {
    groups := make(map[string][]string)
    for _, s := range strs {
        b := []byte(s)
        sort.Slice(b, func(i, j int) bool { return b[i] < b[j] })
        key := string(b) // anagrams share the same sorted letters
        groups[key] = append(groups[key], s)
    }

    out := make([][]string, 0, len(groups))
    for _, g := range groups {
        out = append(out, g)
    }
    return out
}

func main() {
    fmt.Println(groupAnagrams([]string{"eat", "tea", "tan", "ate", "nat", "bat"}))
}

How to Solve

1. Find a signature that all anagrams share. Two words are anagrams exactly when their letters, sorted, are identical — so the sorted string is a perfect canonical key.
2. Bucket by that key. A map[string][]string collects every word under its sorted-letter signature in one pass.
3. Collect the buckets into the result slice. Map iteration order is random in Go, so the groups (and words within them) come out in arbitrary order — which the problem allows.

Complexity

Time: O(n · k log k) for n words of length up to k. Space: O(n · k) for the map and output.