Использование простых чисел для определения анаграмм быстрее, чем цикл?

Question

Недавно у меня был телефон для роли SE, и меня спросили, как бы я определил, были ли два слова анаграммами или нет, я дал ответ, который включал что-то в соответствие с тем, чтобы получить персонажа, итерации над словом, если он существует цикл выхода и т. д. Я думаю, что это было решение N^2 как один цикл за слово с внутренним циклом для сравнения.

После звонка я сделал несколько копаний и написал новое решение; тот, который я планирую передать завтра на следующем этапе интервью, он использует хэш-карту с уникальным простым числом, представляющим каждый символ алфавита. Затем я перебираю список слов, вычисляя значение слова и проверяя, сравнивается ли оно со словом, которое я проверяю. Если значения совпадают, у нас есть победитель (весь бизнес математической теоремы).

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

Я 99% уверен, хэш-карта будет быстрее, но ...

Может кто-нибудь подтвердить или опровергнуть свои подозрения? Спасибо.

Редактировать: Я забыл упомянуть, что сначала проверяю размер слов, прежде чем даже придумываю что-либо.

Answer 1

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

Ваша структура данных - HashMap, которая поддерживает подсчет различных букв. Вы можете добавить буквы от первого слова в O (n) времени. Ключ - это символ, а значение - частота. Если письмо еще не указано в HashMap, то put оно имеет значение 1. Если это так, замените его на value + 1.

При повторении букв второго слова, вычтите один из вашего счета вместо этого, удалив письмо, когда оно достигнет 0.Если вы попытаетесь удалить письмо, которое не существует, вы можете сразу указать, что это не анаграмма. Если вы достигнете конца, а HashMap не пуст, это не анаграмма. Иначе это анаграмма.

В качестве альтернативы вы можете заменить HashMap на массив. Индекс массива соответствует символу, а значение совпадает с предыдущим. Это не анаграмма, если значение падает до -1, и это не анаграмма в конце, если какое-либо из значений не 0.

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

Answer 2

Проблема с умножением заключается в том, что цифры могут стать большими. Например, если буква «c» равна 11, тогда слово с 10 c будет переполнять 32-битное целое число.

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

Если вы используете большие целые числа, то он будет медленно двигаться для длинных слов.

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

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

Пройдите буквы в первом слове, увеличивая количество для каждой буквы. Затем пройдите по буквам во втором слове, уменьшив счет.

Если количество отсчетов достигает нуля в конце этого процесса, то слова являются анаграммами.