Group Anagrams

1. Problem Description

Given an array of strings, group the anagrams together. Anagrams contain the same letters but in a different order.

2. Approach

• Brute force
• hash

3. Implementation

3.1. Brute Force

package main

import "sort"

func groupAnagrams(strs []string) [][]string {
	if len(strs) == 0 {
		return nil
	}

	res := make([][]string, 0)

	visited := make(map[string]bool, 0)
	for i := 0; i < len(strs); i++ {
		runes := []rune(strs[i])
		sort.Slice(runes, func(i, j int) bool {
			if runes[i] < runes[j] {
				return true
			} else {
				return false
			}
		})
		if visited[string(runes)] {
			continue
		}
		group := make([]string, 0)
		group = append(group, strs[i])
		for j := i + 1; j < len(strs); j++ {
			runes2 := []rune(strs[j])
			sort.Slice(runes2, func(i, j int) bool {
				if runes2[i] < runes2[j] {
					return true
				} else {
					return false
				}
			})
			if string(runes2) == string(runes) {
				group = append(group, strs[j])
			}
		}

		res = append(res, group)

		visited[string(runes)] = true

	}
	return res
}

3.2. hash

func groupAnagrams2(strs []string) [][]string {
	if len(strs) == 0 {
		return nil
	}

	res := make([][]string, 0)

	groups := make(map[string][]string, 0)
	for i := 0; i < len(strs); i++ {
		runes := []rune(strs[i])
		sort.Slice(runes, func(i, j int) bool {
			if runes[i] < runes[j] {
				return true
			} else {
				return false
			}
		})
		str := string(runes)
		list, ok := groups[str]
		if ok {
			groups[str] = append(list, strs[i])
		} else {
			groups[str] = []string{strs[i]}

		}
	}

	for _, group := range groups {
		res = append(res, group)
	}

	return res
}

4. References

• 49. Group Anagrams - LeetCode