49. Group Anagrams

medium arrays-hashing

Group strings that are anagrams of each other.

Given an array of strings, group the anagrams together.

Approach

Sort each string to get a canonical key — all anagrams share the same sorted key. Use a hash map keyed by sorted string — O(n·k·log k) time.

Solutions

Ruby

def group_anagrams(strs)
  groups = Hash.new { |h, k| h[k] = [] }
  strs.each do |s|
    key = s.chars.sort.join
    groups[key] << s
  end
  groups.values
end

Python

from collections import defaultdict

def group_anagrams(strs: list[str]) -> list[list[str]]:
    groups = defaultdict(list)
    for s in strs:
        key = "".join(sorted(s))
        groups[key].append(s)
    return list(groups.values())

Go

func groupAnagrams(strs []string) [][]string {
    groups := make(map[string][]string)
    for _, s := range strs {
        key := sortString(s)
        groups[key] = append(groups[key], s)
    }
    result := make([][]string, 0, len(groups))
    for _, v := range groups {
        result = append(result, v)
    }
    return result
}

func sortString(s string) string {
    r := []rune(s)
    sort.Slice(r, func(i, j int) bool { return r[i] < r[j] })
    return string(r)
}

TypeScript

function groupAnagrams(strs: string[]): string[][] {
    const groups = new Map<string, string[]>();
    for (const s of strs) {
        const key = s.split("").sort().join("");
        if (!groups.has(key)) groups.set(key, []);
        groups.get(key)!.push(s);
    }
    return Array.from(groups.values());
}

Elixir

defmodule Solution do
  def group_anagrams(strs) do
    strs
    |> Enum.group_by(fn s ->
      s |> String.graphemes() |> Enum.sort() |> Enum.join()
    end)
    |> Map.values()
  end
end