The next stop on our leetcode conquest is our first medium difficulty problem and a continuation of the easy level "Is Anagram" problem. The problem will function like this: "Given an array of strings "strs" group the strings so that each group member is an anagram of the other. An anagram if you didnt know is a word or for our purposes a string that contains the same frequency of letters as another string not nessesarily in the same order. We will only need to consider lowercase latin characters for this problem. " Our goal for this solution will be to solve with a time complexity of O(n * m) where "n" is the size of the input array and "m" is the size of the longest string.
We will be writing the solution using the Golang programming language which will make our algorithm run blazingly fast. Los anfangen!
First we should decide on our function parameters. We will be taking a string slice as args and returning a slice of string slices as output. We will also initialize a variable wordFreqs which will be a slice of 26 integers arrays representing each latin lowercase letter. We will use these [26]int arrays as keys to group each word together in a map.
func GroupAnagrams(strs []string) [][]string {
var wordFreqs [][26]int
}Now we will iterate over each word and each letter in "strs" and store each word as a [26]int representation inside of "wordFreqs"
func GroupAnagrams(strs []string) [][]string {
var wordFreqs [][26]int
// Iterate over each string and char O(n)
// where n is the number of strings in 'strs';
for i := range strs {
var chrFreq [26]int
// Iterate over each char in 'strs[i]', O(m)
// where m is the longest string in strs;
for _, chr := range strs[i] {
// We subtract by 97 because golang stores runes (chars) as unicode characters
// So unicode "a" 97 should take up position 0 in our [26]int;
chrFreq[chr - 97]++
}
// append is O(1) amortized;
wordFreqs = append(wordFreqs, chrFreq)
}Next we create a map to store our groupings. It will use [26]int keys and hold a string slice as its values:
map[[26]int][]string Crucially each key in our slice wordFreqs has the same index as the original word in "strs" so we can use this to iterate over each key and store them in our map
// Iterate in O(n), n is the size of 'wordFreqs' and also 'strs';
for i := range wordFreqs {
groups[wordFreqs[i]] = append(groups[wordFreqs[i]], strs[i])
}Finally we can convert our map into the expected [][]string and return the groupings
// Iterate over the keys in groups O(k) where k is the
// number of keys in 'groups';
for key := range maps.Keys(groups) {
out = append(out, groups[key])
}In the end our code should look as follows:
func GroupAnagrams(strs []string) [][]string {
var wordFreqs [][26]int
groups := make(map[[26]int][]string)
var out [][]string
// Iterate over each string and char O(n)
// where n is the number of strings in 'strs';
for i := range strs {
var chrFreq [26]int
// Iterate over each char in 'strs[i]', O(m)
// where m is the longest string in strs;
for _, chr := range strs[i] {
chrFreq[chr - 97]++
}
// append is O(1) amortized;
wordFreqs = append(wordFreqs, chrFreq)
}
// Iterate in O(n), n is the size of 'wordFreqs' and also 'strs';
for i := range wordFreqs {
groups[wordFreqs[i]] = append(groups[wordFreqs[i]], strs[i])
}
// Iterate over the keys in groups O(k) where k is the
// number of keys in 'groups';
for key := range maps.Keys(groups) {
out = append(out, groups[key])
}
// Worst Case time cost is O(n * m) where n is the size of 'strs' and
// m is the size of the longest string in 'strs';
return out
}After an algorithm analysis we can see that the most costly portion is our O(n * m) iterator and so we can say we've reach our target time complexity.