Группировка анаграмм
Дан массив строк strs
. Сгруппируйте все анаграммы вместе в подсписки. Вы можете вернуть ответ в любом порядке.
Анаграмма — это строка, которая содержит в точности те же символы, что и другая строка, но порядок символов может быть другим.
Пример 1:
Input: strs = ["eat","tea","tan","ate","nat","bat"] Output: [["eat","tea","ate"],["tan","nat"],["bat"]]
Пример 2:
Input: strs = [""] Output: [[""]]
Пример 3:
Input: strs = ["a"] Output: [["a"]]
Рекомендуемая временная и пространственная сложность
Вам следует стремиться к решению с временной сложностью O(n * k * log(k))
и пространственной сложностью O(n * k)
, где n
— количество строк, а k
— максимальная длина строки.
Подсказка 1
Как определить, являются ли две строки анаграммами? Что общего у всех анаграмм одной и той же строки?
Подсказка 2
Можно ли преобразовать каждую строку так, чтобы все анаграммы давали одинаковый результат? Подумайте о сортировке символов.
Подсказка 3
Отсортированные символы анаграмм образуют одинаковую строку. Используйте эту строку как ключ в хеш-таблице для группировки анаграмм.