Table of Contents
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