Статьи Утилиты Telegram YouTube Отзывы

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

Видеогайд

21 февраля 2023

Тэги: Collections, Java, алгоритмы, головоломки.

Содержание

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

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

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

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

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

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

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

private Map<Character, Integer> getLetterStat(String word) {
    var stat = new HashMap<Character, Integer>();
    for (int i = 0; i < word.length(); i++) {
        char c = word.charAt(i);
        stat.put(c, stat.getOrDefault(c, 0) + 1);
    }
    return stat;
}

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

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

public boolean isAnagram(String left, String right) {
    if (left.length() != right.length()) {
        return false;
    }
    var leftStat = getLetterStat(left);
    var rightStat = getLetterStat(right);
    return leftStat.equals(rightStat);
}

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

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

System.out.println(isAnagram("фара", "арфа")); // true
System.out.println(isAnagram("каркас", "краска")); // true
System.out.println(isAnagram("север", "сервер")); // false, разная длина
System.out.println(isAnagram("север", "ветер")); // false, разные буквы

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

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

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

public boolean isAnagram(String left, String right) {
    if (left.length() != right.length()) {
        return false;
    }
    char[] chars1 = left.toCharArray();
    Arrays.sort(chars1);

    char[] chars2 = right.toCharArray();
    Arrays.sort(chars2);
    return Arrays.equals(chars1, chars2);
}

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

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


Облако тэгов

Kotlin, Java, Spring, Spring Boot, Spring Data, SQL, PostgreSQL, Oracle, Linux, Hibernate, Collections, Stream API, многопоточность, файлы, Nginx, Apache, maven, gradle, JUnit, YouTube, новости, руководство, ООП, алгоритмы, головоломки, rest, GraphQL, Excel, XML, json, yaml.

Последние статьи


Комментарии

04.05.2023 17:07 Евгений

Вот моя реализация для Kotlin:

fun isAnagram(first: String, second: String): Boolean {
        if (first.length != second.length)
            return false
        val secondList = second.toMutableList()
        first.forEach {
            val ind = secondList.indexOf(it)
            if (ind > -1){
                secondList.removeAt(ind)
            }else{
                return false
            }
        }
        return true
    }

06.05.2023 00:34 devmark

Евгений, такая версия тоже работает, но я хотел бы обратить внимание на пару моментов.
Первое - это использование метода indexOf() на List в цикле. Неявно там внутри цикл, поэтому получается цикл в цикле, что не очень хорошо с точки зрения алгоритма.
Второе - это использование метода removeAt(). Конечно, зависит от конкретной реализации, но также не самая оптимальная операция для списков. Для ArrayList приходится каждый раз сдвигать все элементы, находящиеся правее указанного.
В идеале, к каждому символу из first и second мы должны обращаться только один раз.

10.05.2023 00:11 Евгений

Согласен, спасибо за комментарий решения!

14.06.2024 14:06 juniorjava

Подскажите, а если на вход будут подаваться 2 строки не равной длины, а, например: "мадагаскар" и "маска" или "мадагаскар" и "карта". И проверить нужно, что из слова "мадагаскар" можно составить слово "маска", но нельзя "карта", то как после подчсета в каждом слове каждой буквы сравнить 2 мапы?

14.06.2024 14:12 devmark

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

Добавить комментарий

×

devmark.ru