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

Постановка задачи

strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

[["bat"], ["nat","tan"], ["ate", "eat", "tea"]]

strs = ["act", "pots", "tops", "cat", "stop", "hat"]

[["hat"], ["act", "cat"], ["stop", "pots", "tops"]]

Решение

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

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

С точки зрения алгоритмов, задача требует реализовать отношение эквивалентности. Нужно определить правило, по которому два разных объекта считаются одинаковыми.

Хотя вряд ли мы будем искать анаграммы в коммерческой разработке каждый день, механика этой задачи используется повсеместно:

1. Дедупликация и поиск похожих данных. Представим, что пользователь вводит адрес: "ул. Кормена, д. 10" и "Кормена 10, ул". Система должна понять, что это идентичные записи. Алгоритм "группировки" помогает нормализовать данные и объединить дубликаты.

2. Кэширование с нормализацией. Если API принимает параметры в URL (например, ?color=red&size=M и ?size=M&color=red), сервер должен понимать, что это один и тот же запрос. Группировка (нормализация ключей параметров) позволяет эффективно кэшировать результат.

3. Анализ логов и группировка ошибок. В системах мониторинга, таких как Sentry или ELK, тысячи ошибок могут отличаться только переменными, например ID пользователя или время. Алгоритм нормализует текст ошибки, убирая уникальные детали, и использует результат как ключ для группировки. Это позволяет показать не 1000 разных строк, а одну ошибку с пометкой "случилось 1000 раз".

Решение "в лоб" - это перебор каждого слова в массиве и сравнение его со всеми остальными. Берем первое слово. Бежим по остальному массиву и проверяем, является ли другое слово анаграммой. Если да - кладем в одну группу. Минус такого решения уже очевиден - оно очень медленное. Сложность будет явно не лучше O(n²), так как мы каждую строку сравниваем с каждой.

Давайте подумаем, как можно решить задачу эффективнее.

Идея решения:

Для эффективной группировки элементов мы можем использовать хеш-таблицу. Если мы сможем для любой строки определенным образом формировать ключ так, чтобы для анаграмм получалось одно и то же значение ключа, то хеш-таблица поможет эффективно находить нужную группу для текущей строки без перебора всех строк. Таким образом, нам будет достаточно одного прохода по массиву строк и не нужно будет сравнивать каждую строку с каждой.

Теперь главный вопрос: как можно формировать ключ для хеш-таблицы?

Для начала давайте подробнее разберемся, что такое анаграммы. Чтобы одно слово считалось анаграммой другого, должны соблюдаться два условия:

• идентичный состав, используются ровно те же буквы и в том же количестве
• ничего лишнего, нельзя добавлять новые буквы или выбрасывать имеющиеся

То есть для анаграмм отличается лишь порядок букв, но сами буквы и их количество должны быть одинаковыми.

Это дает нам идею для формирования ключа: для строки мы собираем таблицу частот каждой буквы в строке и затем из этой таблицы частот создаем ключ.

Как можно создать ключ из таблицы частот букв?

Вспомним задачу "Записка о выкупе" - там для таблицы частот мы использовали массив из 26 элементов, где каждый элемент массива содержал частоту определенной буквы английского алфавита. Такой массив как раз и можно использовать для ключа (преобразовав его в кортеж или строку), перечислив по порядку элементы через запятую.

Например, если у нас есть строка "bada", мы проходим по этой строке и заполняем массив из 26 элементов (таблицу частот): [2, 1, 0, 1, 0, 0, ..., 0], далее преобразуем этот массив в кортеж или строку: "2,1,0,1,0,0,...,0" и получаем ключ.

Важный момент - использование разделителей. При преобразовании таблицы частот в строку простой формат, такой как конкатенация без разделителей, может привести к одинаковым ключам для разных групп анаграмм. Например, значения [1, 11] и [11, 1] могут дать одну и ту же строку "111".

Основные шаги:

1. Создаем хеш-таблицу для групп. В качестве ключа - частота букв в анаграмме, значением будет список строк - группа анаграмм.

2. Идем циклом по массиву строк. Для каждой отдельной строки:

   • Получаем ключ
   • Добавляем строку в соответствующую ключу группу

3. Получаем результат. После завершения цикла хеш-таблица будет заполнена группами. Соберем все значения (списки строк) в один общий список списков.

Давайте разберем, как это работает на примере:

strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

Для краткости ключ будем представлять как строку с отсортированными буквами.

1. Создаем хеш-таблицу для групп. Изначально у нас пустая хеш-таблица groups = {}.

2. Идем циклом по массиву строк.

   2.1 Слово "eat" - Получаем ключ: "aet" - Добавляем в группы: {"aet": ["eat"]}

   2.2 Слово "tea" - Ключ: "aet" - Ключ "aet" уже есть. Добавляем слово в группу: {"aet": ["eat", "tea"]}

   2.3 Слово "tan" - Ключ: "ant" - Добавляем в группы: {"aet": ["eat", "tea"], "ant": ["tan"]}

   2.4 Слово "ate" - Ключ: "aet" - Добавляем в группы: {"aet": ["eat", "tea", "ate"], "ant": ["tan"]}

   2.5 Слово "nat" - Ключ: "ant" - Добавляем в группы: {"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"]}

   2.6 Слово "bat" - Ключ: "abt" - Добавляем в группы: {"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"], "abt": ["bat"]}

3. Получаем результат.

   • Берем все значения (списки) из нашей таблицы групп:
     • ["eat", "tea", "ate"]
     • ["tan", "nat"]
     • ["bat"]

Итог: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]].

Порядок групп в итоговом массиве не важен. Порядок слов внутри каждой группы тоже не важен.

Оценка сложности

При использовании таблицы частот (массива из 26 целых чисел) оценка сложности выглядит следующим образом.

Пусть:

• n - количество строк во входном массиве.
• m - максимальная длина одной строки.

Временная сложность

Для каждого из n слов мы проходим по всем его символам, чтобы получить ключ: O(m). Кладем слово в хеш-таблицу. Поиск и вставка в среднем занимают O(1) (в худшем случае зависит от хеш-функции, но для ключей-строк длиной 26 это работает очень быстро).

Таким образом, получаем O(n * m).

Пространственная сложность

Мы тратим память на следующие структуры:

• Хеш-таблица: в худшем случае (если анаграмм нет вообще) в таблице будет n ключей. Каждый ключ - это массив из 26 чисел, что является константой O(1).
• Хранение строк: мы храним все исходные строки в списках внутри таблицы. Суммарное количество символов во всех строках - O(n * m).
• Массив частот: временный массив freq занимает O(26), что является константой O(1).

Таким образом, общий объем памяти напрямую зависит от объема входных данных, то есть O(n * m).

Код решения

Приведем код решения.

func groupAnagrams(strs []string) [][]string {
    groups := map[[26]int][]string{}
    for i := 0; i < len(strs); i++ {
        key := getKey(strs[i])
        groups[key] = append(groups[key], strs[i])
    }
    result := [][]string{}
    for _, v := range groups {
        result = append(result, v)
    }
    return result
}
 
func getKey(s string) [26]int {
    freq := [26]int{}
    for i := 0; i < len(s); i++ {
        freq[s[i] - 'a']++
    }
    return freq
}
 

Итоги

Задача является фундаментальной для понимания работы с хеш-таблицами и техник оптимизации алгоритмов.

1. Ключевая идея. Главный секрет решения - формирование ключа. Чтобы сгруппировать разные строки (анаграммы), их нужно привести к единому "эталону" (ключу). Cпособы создания ключа:

   • Сортировка: легко реализовать, подходит для коротких строк.
   • Таблица частот: подходит для длинных строк и больших наборов данных.

2. Уроки для интервью.

   • Избегаем коллизий: если строим ключ-строку из чисел, всегда используем разделители (например, ","), чтобы [1, 11] не превратилось в то же самое, что и [11, 1].
   • Знание языка: помним, какие типы данных могут быть ключами в конкретном языке (например, [26]int в Go, tuple в Python и List в Java работают по-разному).
   • Компромисс: мы осознанно тратим дополнительную память на хеш-таблицу, чтобы радикально ускорить время выполнения по сравнению с наивным решением.

3. Практическая ценность. Метод группировки через нормализацию ключей используется в реальных системах для дедупликации данных, анализа логов, поиска похожих товаров в e-commerce и даже в биоинформатике при анализе последовательностей ДНК.