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

Question

По заданному набору слов сгруппируйте анаграммы IP:{tar,rat,banana,atr} OP:{[tar,rat,atr],[banana]}

Одно из решений этого вопроса с использованием Hash Table. рассмотрите каждое слово, отсортируйте его и добавьте в качестве ключа к хэш-таблице, если она отсутствует. Значение для ключа будет список всех анаграмм с тем же ключом. Я хотел знать о временных сложностях. Чтобы отсортировать символы в массиве, предположим, что O(n log n) Для сохранения в хеш-таблице это будет O(n), всего O(n*nlogn).

Есть ли лучший алгоритм? с меньшей сложностью времени?

Answer 1

Из-за сложности времени, вы всегда можете использовать сортировку подсчета для сортировки отдельных слов, которые стоят только линейное время на слово. Вы также можете сначала посчитать вхождения букв, а затем хэшировать количество вхождений вместо отсортированного слова, что по сути то же самое, что и сортировка за вычетом шага перестроения.

Но так как слова, как правило, будут короткими, это может не принести вам никаких практических преимуществ.