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

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

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

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


sorting algorithm anagram
person user2626431    schedule 29.07.2013    source источник
comment
Но n — это длина слова, а не количество слов в вашем массиве, так что это не должно быть слишком плохо. Тем не менее, вы можете определить свою собственную хэш-функцию, независимую от перестановок. Например, сложим буквенные значения: tar -> 20+1+18=39. Но это может быть не очень хороший хэш.   -  person Teepeemm    schedule 30.07.2013
comment
Я не вижу связи между этим вопросом и дубликатом. См. здесь хэш, не зависящий от порядка. Тестовое приложение, которое я написал, сбрасывало хэши и слова, и я отсортировал их по хешу, чтобы сгруппировать анаграммы вместе, что, похоже, и есть ваш путь.   -  person sh1    schedule 10.08.2013

Ответы (1)


arrow_upward
1
arrow_downward

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

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

person zw324    schedule 29.07.2013
comment
+1. с точки зрения нотации большого O решение для подсчета частоты букв и последующего их хеширования, безусловно, лучше, чем O (N * M * lg (M)), где M - длина самой длинной строки. Потому что, согласно вашему решению, оно имеет O(26*NM) = O(NM). Но я согласен с вами, что это не даст никакого практического преимущества (даже если N и M малы, это может работать хуже, чем то, что сейчас делает OP) :) - person Fallen; 30.07.2013
comment
Ну, это был вопрос интервью, и я закодировал ответ, который описал в своем вопросе. Но я не очищаю интервью. Поэтому хотел узнать, есть ли что-то лучше. - person user2626431; 30.07.2013
comment
Слишком много факторов для собеседования, например, насколько хороша программа, которую вы написали? Сдали хороший анализ? Вы были хорошим культурным парнем? Но с точки зрения алгоритма ответа, который вы дали, должно быть достаточно. - person zw324; 30.07.2013
comment
Ну, у меня была одна небольшая ошибка, которую я исправил после того, как он попросил просмотреть мой код. Корю себя за это буквально. Почти уверен, что все остальное было хорошо. - person user2626431; 30.07.2013