49. Group Anagrams #

Problem #

Given an array of strings, group anagrams together.

Example:

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

Note:

• All inputs will be in lowercase.
• The order of your output does not matter.

Problem Summary #

Given an array of strings, group the strings in the array that have an Anagrams relationship. An Anagrams relationship means that two strings contain exactly the same characters in a different order; they are composed of permutations and combinations of each other.

Solution Approach #

For this problem, we can sort each string. After sorting, strings that are the same Anagrams will necessarily have the same sorted result. Use the sorted string as the key and store it in a map. After traversing the array, we can obtain a map where the key is the sorted string and the value corresponds to the collection of Anagrams strings for that sorted string. Finally, output the string arrays corresponding to these values.

Code #

package leetcode

import "sort"

type sortRunes []rune

func (s sortRunes) Less(i, j int) bool {
	return s[i] < s[j]
}

func (s sortRunes) Swap(i, j int) {
	s[i], s[j] = s[j], s[i]
}

func (s sortRunes) Len() int {
	return len(s)
}

func groupAnagrams(strs []string) [][]string {
	record, res := map[string][]string{}, [][]string{}
	for _, str := range strs {
		sByte := []rune(str)
		sort.Sort(sortRunes(sByte))
		sstrs := record[string(sByte)]
		sstrs = append(sstrs, str)
		record[string(sByte)] = sstrs
	}
	for _, v := range record {
		res = append(res, v)
	}
	return res
}