Оптимизация поиска анаграмм
От: Artem Korneev США https://www.linkedin.com/in/artemkorneev/
Дата: 03.04.17 17:41
Оценка: 2 (1)
Получил недавно любопытное задание на интервью. Вот текст задания:

Anagrams are defined as words with the same length and same number of characters in any order.
Eg:
bat/tab/abt are anagrams
aabb/baba/bbaa/abab — anagrams
abcd/abce — are not anagrams (different characters)
aaab, aabb — are not anagrams (different character count)

Given a list of words — { abcd, bbb, abc, bat, cat, yyyyxxxx, tab, atb, rat, cab, xxyyxxyyxx, atb }
Print out the anagram pairs — {{abc, cab}, {bat, tab, atb, atb}}

Assuming that the input is of type [a-z], can you optimize the solution.


С анаграммами всё просто — они легко находятся, если сравнивать отсортированные копии строк. А вот с оптимизацией я так и не разобрался. Я так понимаю, смысл там в генерации уникального хэша для каждой строки, но как сделать хэш одинаковым для разных строк, содержащих тот же набор букв, я пока не понял.
Коллега взглянул и сказал, мол, "о, тут всё просто — надо использовать простые числа". Если я правильно понимаю, в этом варианте нужно выбирать простые числа от 2 и более (а может и от 3, не уверен) и брать результат умножения. Но 26-е простое число в этом варианте будет 101, т.е. для каждого 'z' нам нужно умножать хэш на 101. Тогда 6..7 букв 'z' дадут хэш, который вылезет за пределы 64 bit.

Подскажите, какой тут был бы правильный алгоритм? И, что более интересно — подскажите, какие ещё полезные способы хэширования стоит посмотреть чтобы лучше понимать эту тему?
С уважением, Artem Korneev.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.