Group Anagrams - Go Solution

LeetCode

— 1 min read

Solving the LeetCode "Group Anagrams" Problem in Go

Difficulty: Medium | Tags: Array, Hash Table, String, Sorting

Introduction

Anagrams are words formed by rearranging the letters of another word, using all the original letters exactly once. The problem requires grouping anagrams from a given list of strings efficiently.

Problem Analysis

Given an array of strings, we need to group strings that are anagrams of each other. For example, "eat", "tea", and "ate" are anagrams because they contain the same letters in different orders. The solution must efficiently categorize these strings into groups.

Solution Approach

The optimal approach involves using a hash map to group anagrams. The key idea is to use a sorted version of each string as the map key. Strings that are anagrams will produce the same sorted key, allowing us to group them together. This approach leverages sorting and hashing for efficient grouping.

Go Implementation


package main
import (
"sort"
"strings"
)
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 _, group := range groups {
        result = append(result, group)
    }
    return result
}
func sortString(s string) string {
    chars := strings.Split(s, "")
    sort.Strings(chars)
    return strings.Join(chars, "")
}

Complexity Analysis

Time Complexity: O(N * K log K), where N is the number of strings and K is the maximum length of a string. Sorting each string takes O(K log K) time, and we do this for all N strings.

Space Complexity: O(N * K), as we store all strings in the hash map, with each string potentially of length K.

Testing and Examples

Example 1: Input: ["eat","tea","tan","ate","nat","bat"] → Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2: Input: [""] → Output: [[""]]

Example 3: Input: ["a"] → Output: [["a"]]

Best Practices and Tips

1. Use sorting to generate consistent keys for anagrams. 2. Leverage Go's built-in map and slice operations for efficient grouping. 3. Consider edge cases like empty strings or single-character strings.

Read more