Table of Contents
Anagram
What is an Anagram?
An anagram is a word or phrase formed by rearranging the letters of another word or phrase, typically using all the original letters exactly once.
Example
- Input:
"listen"and"silent" - Output: They are anagrams because rearranging the letters of
"listen"gives"silent".
Group Anagrams
Group Anagrams involves taking a list of words and grouping them into subsets of anagrams.
Input
["eat", "tea", "tan", "ate", "nat", "bat"]Output
[["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]Here,
"eat","tea", and"ate"are anagrams."tan"and"nat"are anagrams."bat"has no anagram.
Logic
- Canonical Form:
- Each word is converted to its “sorted” version (e.g.,
"eat"→"aet") to serve as a unique key for grouping anagrams.
- Each word is converted to its “sorted” version (e.g.,
- Mapping:
- Words with the same sorted version are added to the same group in a map.
- Final Output:
- Extract values from the map to form the result.
Golang code
package main
import (
"fmt"
"sort"
)
// Helper function to sort a string
func sortString(s string) string {
r := []rune(s)
sort.Slice(r, func(i, j int) bool { return r[i] < r[j] })
return string(r)
}
// Function to group anagrams
func groupAnagrams(strs []string) [][]string {
anagramMap := make(map[string][]string)
for _, str := range strs {
// Sort the string to get its canonical form
sorted := sortString(str)
// Group by the sorted string
anagramMap[sorted] = append(anagramMap[sorted], str)
}
// Convert map values to a slice of slices
result := [][]string{}
for _, group := range anagramMap {
result = append(result, group)
}
return result
}
func main() {
words := []string{"eat", "tea", "tan", "ate", "nat", "bat"}
grouped := groupAnagrams(words)
fmt.Println(grouped)
}
Output
[[eat tea ate] [tan nat] [bat]]
Leave a Reply