Group Anagrams

Leetcode#49

Group Anagrams

Problem Statement

Given an array of strings strs, group the anagrams together.

You can return the answer in any order.

Example 1:

Input: strs = [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”]

Output: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]

Explanation:

  • There is no string in strs that can be rearranged to form "bat".
  • The strings "nat" and "tan" are anagrams as they can be rearranged to form each other.
  • The strings "ate""eat", and "tea" are anagrams as they can be rearranged to form each other.

Example 2:

Input: strs = [“”]

Output: [[“”]]

Example 3:

Input: strs = [“a”]

Output: [[“a”]]

Constraints:

  • 1 <= strs.length <= 104
  • 0 <= strs[i].length <= 100
  • strs[i] consists of lowercase English letters.

Simple Approach

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

    // stores the final result
	result := [][]string{}

    // cache used to compare if input is already seen in anagram cache
	cacheMap := map[string][]string{}

	for i := 0; i < len(strs); i++ {
        // sort the string using present char incremental order
		tempSortedStr := sortString(strs[i])

        // update the similar str list against a anagram combination
		cacheMap[tempSortedStr] = append(cacheMap[tempSortedStr], strs[i])
	}

	for _, values := range cacheMap {
		result = append(result, values)
	}
	return result
}

func sortString(inputStr string) string {
	sortedStr := []byte(inputStr)
	sort.Slice(sortedStr, func(i, j int) bool {
		return sortedStr[i] < sortedStr[j]
	})
	return string(sortedStr)
}

Output

Input
strs =
["eat","tea","tan","ate","nat","bat"]

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

Optimised solution

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

	anagramMap := make(map[string][]string)

	for _, strEntry := range strs {

		freqMap := make([]int, 26)
		for _, ch := range strEntry {
			freqMap[ch-'a']++
		}

		keyString := getKey(freqMap)
		anagramMap[keyString] = append(anagramMap[keyString], strEntry)
	}

	for _, values := range anagramMap {
		result = append(result, values)
	}

	return result
}

func getKey(freqMap []int) string {
	keyByte := make([]byte, len(freqMap))
	for index, count := range freqMap {
		if count > 0 {
			keyByte = append(keyByte, byte(index+'a'), byte(count+'0'))
		}
	}
	return string(keyByte)
}

Output

Input
strs =
["eat","tea","tan","ate","nat","bat"]

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

Please visit https: https://codeandalgo.com for more such contents.

Leave a Reply

Your email address will not be published. Required fields are marked *