Сборка слов‑анаграмм в группы

Условие

Реализуйте функцию (без необходимости объявлять класс или импортировать пакеты), принимающую массив строк и возвращающую двумерный массив, где каждый вложенный массив содержит набор слов‑анаграмм — слов, состоящих из одинаковых символов.

func groupAnagrams(arr []string) [][]string{
    
}

Ответ

Ключом группы сделайте отсортированные символы слова. При запрете импортов можно отсортировать []rune простым insertion sort; это сохраняет поддержку Unicode-кодовых точек.

Функция без дополнительных пакетов:

func groupAnagrams(arr []string) [][]string {
    groups := make([][]string, 0)
    indexes := make(map[string]int)
    for _, word := range arr {
        chars := []rune(word)
        for i := 1; i < len(chars); i++ {
            value, j := chars[i], i
            for j > 0 && chars[j-1] > value {
                chars[j] = chars[j-1]
                j--
            }
            chars[j] = value
        }
        key := string(chars)
        index, ok := indexes[key]
        if !ok {
            index = len(groups)
            indexes[key] = index
            groups = append(groups, nil)
        }
        groups[index] = append(groups[index], word)
    }
    return groups
}

Порядок групп — первое появление, регистр значим, нормализация Unicode не выполняется. Сортировка слова длины k занимает O(k²); с разрешённым sort можно получить O(k log k).