Solution to problem 49 “Group Anagrams” from LeetCode.

Problem Statement

Given an array of strings. Group anagrams together.

Note:

• all letters are lowercase
• order doesn’t matter

Example

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

Solution

Sort the array =)

Algorithm idea:

Write a function that, given a word, returns a word with the same letters, but with letters sorted in ascending order.

Create a collection where the key will be the word after sorting the letters, and the value will be an array of words consisting of the letters of that word.

Go through all the source words, get the sorting of letters in the word - add the word to the corresponding element of the collection.

And then just create a resulting array of arrays of strings. Go through the collection, taking each array and adding it to the resulting one.

In short: group words by the letters they consist of.

func groupAnagrams(strs []string) [][]string {
    words := make(map[string][]string,0)
    for idx := range strs {
        jdx := orderLetter(strs[idx])
        if _, ok:= words[jdx];!ok {
            words[jdx] = make([]string,0)
        }
        words[jdx] = append(words[jdx] ,strs[idx])
    }
    res := make([][]string,0)

    for idx := range words{
        res = append(res,words[idx])
    }

    return res
}

func orderLetter(s string) string {
    o := []byte(s)

    for idx := 0; idx<len(o);idx++ {
        k := idx
        for jdx:=idx-1;jdx>=0;jdx-- {
            if o[jdx]>o[k] {
                tmp := byte(o[jdx])
                o[jdx] = byte(o[k])
                o[k] = tmp
                k = jdx
            }
        }
    }
    return string(o)
}