Group Anagrams | DSA Journal

Question

You're given a list of strings. Group them together so that each group contains words that are anagrams of each other.

An anagram means the same letters in a different order. Return the grouped results as a list of string arrays.

Example

Input: ["eat", "tea", "tan", "ate", "nat", "bat"]

Output: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Explanation: Each group contains words made from the same letters.

Input: [""]

Output: [[""]]

Input: ["a"]

Output: [["a"]]

My Notes

Two words are anagrams if their sorted characters are the same.
Use the sorted string as a key to group original words in a map.
Append the word to the group corresponding to its key.
At the end, return all the map values as groups.
Time complexity is O(n * k log k) where k is the average word length (due to sorting).

Visual

package main

import (
    "fmt"
    "sort"
    "strings"
)

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

func groupAnagrams(strs []string) [][]string {
    lookup := make(map[string][]string)

    for _, item := range strs {
        arr := strings.Split(item, "")
        sort.Strings(arr)
        key := strings.Join(arr, "")
        lookup[key] = append(lookup[key], item)
    }

    ans := [][]string{}
    for _, value := range lookup {
        ans = append(ans, value)
    }
    return ans
}