Алгоритм определения анаграмм

Содержание

1. Реализация с мапой
2. Реализация с сортировкой

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

Одно слово является анаграммой другого, если второе слово получается из первого путём перестановки букв. Например, слово «фара» является анаграммой слова «арфа». Также «комар» является анаграммой слова «корма».

При этом если в слове встречается несколько одинаковых букв, то должно совпадать также их количество. Например, «каркас» и «краска» имеют по две буквы «а» и «к».

Реализация с мапой

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

Напишем вспомогательный метод getLetterStat(), принимающий на вход строку и возвращающий мапу со статистикой.

В цикле проходимся по каждому символу исходной строки с помощью метода charAt(). Затем в нашей мапе со статистикой ищем данный символ среди ключей. По этому ключу получаем уже найденное количество повторений данного символа. Если символа в мапе ещё нет – по умолчанию принимаем его равным 0. Ну и затем просто увеличиваем на 1 количество повторений.

Теперь реализуем сам метод isAnagram(). Он принимает две строки left и right и возвращает true, если слова являются анаграммами друг друга.

Сперва проверяем, что у них одинаковая длина. Затем получаем статистику по каждому из двух слов. В результате мы просто сравниваем между собой две полученные мапы по статистикой с помощью метода equals(). В случае анаграмм у них должны быть одинаковые ключи и значения.

Осталось протестировать нашу реализацию.

Если сравнивать две случайные строки длиной по 10 миллионов букв каждая, то данный алгоритм у меня отрабатывает за 600 миллисекунд, т.е. достаточно быстро. Но можно ещё быстрее.

Реализация с сортировкой

Можно написать ещё более быструю реализацию. Она основана на том, что мы не будем собирать статистику по каждому символу. Вместо этого просто возьмём две исходные строки, преобразуем их в массивы символов и каждый такой массив отсортируем. В случае анаграмм два отсортированных массива символов должны быть равны между собой.

Первым шагом мы также проверяем, что длина исходных строк одинаковая. Затем с помощью метода toCharArray() получаем массив символов для каждой из двух строк. После этого сортируем каждый массив с помощью метода Arrays.sort(). Обратите внимание, что данный метод не создаёт новый массив, а модифицирует исходный. В конце проверяем равенство двух массивов с помощью метода Arrays.equals().

Данная реализация для двух строк по 10 миллионов символов каждая работает не дольше 150 миллисекунд. То есть мы получаем прирост по скорости в 4 раза!