Решение задачи 49 “Group Anagrams” с LeetCode.

Условие задачи

Дан массив строк. Необходимо сгруппировать анаграммы вместе.

Замечение:

• все буквы в нижнем регистре
• порядок сортировки неважен

пример

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

Решение

Отсортировать массив =)

Идея алгоритма:

Написать функцию, которая по заданному слову, возвращает слово с этиме же буквами, но буквы отсортированы по возрастанию.

Создать коллекцию, где ключом будет слово после сортировки букв, а значением - массив слов, состоящий из букв этого слова.

Пройтись по всем исходным словам, получить сортировку букв в слове - добавить слово в соответствующий элемент коллекции.

А потом просто создать результирующий массив массивов строк. Пройтись по коллекции , забирая каждый массив и добавляя его в результирующий.

Кратко: сгруппировать слова по буквам из которых они состоят.

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)
}