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

Учитывая массив слов, сгруппировать анаграммы IP: {деготь, крыса, банан, ATR} ОП: {[деготь, крыса, ртд], [банан]}Группировка анаграммы

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

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

источник

2013-07-29 user2626431

Но 'n' - это длина слова, а не количество слов в вашем массиве, поэтому это не должно быть слишком плохо. Независимо от этого, вы можете определить свою собственную хеш-функцию, которая не зависит от перестроек. Например, добавьте значения букв: tar -> 20 + 1 + 18 = 39. Но это может быть не очень хороший хеш. – Teepeemm

Я не вижу отношения между этим вопросом и дураком. См. [Здесь] (http://stackoverflow.com/a/18144931/2417578) для хэша-агностика заказа. В тестовом приложении я написал сбрасываемые хэши и слова, и я решил, что хэш объединяет анаграммы вместе, что похоже на то, как вы направляетесь. – sh1

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

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

источник

2013-07-29 21:42:18

+1. в терминах большой записи O решение для подсчета частоты букв и последующего ее хэширования, безусловно, лучше, чем O (N * M * lg (M)), где M - длина самой длинной строки. Потому что согласно вашему решению, он имеет O (26 * N * M) = O (N * M). Но я согласен с вами в том, что он не будет покупать никаких практических преимуществ (даже если N и M малы, он может работать хуже, чем сейчас делает OP) :) – Fallen

Ну, это был вопрос интервью, и я закодировал ответ что я описал в своем вопросе. Но я ясно дал интервью. Поэтому хотелось узнать, существует ли что-то лучше. – user2626431

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

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

ответ

Смежные вопросы