Task Livecoding Java Group Anagrams | IT Ментор

88. Группировка анаграмм #

Условие задачи:
Написать только функцию. На входе массив строк, на выходе сгруппированная структура. Тип выходных данных определяешь сам. Потом скажешь, почему используешь эту структуру. Могут быть записи с повторяющимися элементами. Вывод отсортировать лексикографически. Чем лучше по оценке скорости алгоритма, тем лучше

Дан массив строк, необходимо сгруппировать анаграммы
Слово X является анаграммой Y, если одно может быть получено из другого перестановкой букв
В итоговом массиве каждый массив анаграмм должен быть отсортирован в лексикографическом порядке

Пример:

Ввод:
['eat', 'tea', 'tan', 'ate', 'nat', 'batq']

Вывод:
[
    ['ate', 'eat', 'tea'],
    ['nat', 'tan'],
    ['batq']
]

Спойлеры к решению

Подсказки

💡 Нужен ключ, который однозначно представит “форму” слова (его буквы и их количество).
💡 Вариант 1 (проще): отсортировать буквы в слове → "eat" → "aet". Все анаграммы дадут одинаковый ключ.
💡 Вариант 2 (быстрее): посчитать частоты букв (массив int[26]) и сделать строковый ключ вроде "1#0#2#...". Это даёт O(n * L) вместо O(n * L log L).
💡 Удобно использовать Map<key, List<String>>, а в конце вернуть List<List<String>>.
💡 Не забудь отсортировать внутри каждой группы (Collections.sort(...)).

Решение

// Предполагаем, что слова состоят из строчных латинских букв a-z.
// Возвращаем List<List<String>> — естественное представление "список групп строк".
public static List<List<String>> groupAnagrams(String[] words) {
    if (words == null || words.length == 0) {
        return List.of();
    }

    // Ключ -> список анаграмм
    Map<String, List<String>> groups = new HashMap<>();

    for (String word : words) {
        // частоты букв: index = буква - 'a'
        int[] freq = new int[26];
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            // если нужно поддержать другие символы, этот подход надо расширять
            freq[c - 'a']++;
        }

        // строим строковый ключ из частот
        StringBuilder keyBuilder = new StringBuilder();
        for (int count : freq) {
            keyBuilder.append(count).append('#');
        }
        String key = keyBuilder.toString();

        groups.computeIfAbsent(key, k -> new ArrayList<>())
              .add(word);
    }

    // итог: сортируем каждую группу лексикографически
    List<List<String>> result = new ArrayList<>(groups.size());
    for (List<String> group : groups.values()) {
        Collections.sort(group);
        result.add(group);
    }

    return result;
}

Почему именно такая структура и алгоритм:

✅ Map<String, List<String>> как промежуточная структура
- String-ключ — “форма” слова (его буквенный состав).
- List<String> — все слова, которые разделяют эту форму, то есть анаграммы.
✅ List<List<String>> как возвращаемый тип
- Естественное представление: “список групп строк”.
- Удобно и для вывода, и для дальнейшей обработки.
⚙️ Сложность алгоритма:
- Для каждого слова длины L мы:
  - Один раз проходим по буквам → O(L),
  - Строим ключ из 26 элементов → O(26) ~ O(1).
- Итого по всем словам (n слов): O(n * L) по времени.
- По памяти: храним все слова + карту ключей ~ O(n * L).

Для собеседования можно отдельно упомянуть, что:

Более простой, но медленный вариант — сортировать буквы в каждом слове (O(L log L) на слово).
Текущий вариант с частотами букв асимптотически быстрее при длинных словах.