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

49. Сгруппировать анаграммы

Условие задачи:
Дан массив строк. Необходимо сгруппировать слова, являющиеся анаграммами друг друга.

Внутри каждой группы слова должны быть отсортированы лексикографически. Повторяющиеся элементы необходимо сохранить.

Предполагается, что строки состоят из строчных латинских букв a-z.

Код:

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

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

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

Подсказки

💡 Анаграммы содержат одинаковое количество каждой буквы.
💡 Частоты букв можно хранить в массиве int[26].
💡 На основе массива частот сформируй ключ для Map.
💡 Значением карты будет список слов с одинаковым ключом.
💡 После группировки отсортируй слова внутри каждой группы.

Решение

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) {
        int[] frequencies = new int[26];

        for (int i = 0; i < word.length(); i++) {
            frequencies[word.charAt(i) - 'a']++;
        }

        StringBuilder key = new StringBuilder();

        for (int frequency : frequencies) {
            key.append(frequency).append('#');
        }

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

    List<List<String>> result =
            new ArrayList<>(groups.values());

    for (List<String> group : result) {
        Collections.sort(group);
    }

    result.sort(
            Comparator.comparing(group -> group.get(0))
    );

    return result;
}

Map<String, List<String>> подходит для группировки:

ключ описывает количество каждой буквы в слове;
значение содержит все слова с таким набором букв;
повторяющиеся слова сохраняются в списке.

List<List<String>> естественно представляет итоговый список групп.

Построение групп выполняется за O(S), где S — суммарное количество символов во всех строках. Дополнительно требуется время на обязательную лексикографическую сортировку слов внутри групп.

Дополнительная память — O(S) для хранения результата и ключей групп.