Вывод строки в Java: как определить, является ли строка анаграммой? | OTUS
🔥 Начинаем BLACK FRIDAY!
Максимальная скидка -25% на всё. Успейте начать обучение по самой выгодной цене.
Выбрать курс

Курсы

Программирование
iOS Developer. Basic
-25%
Python Developer. Professional
-25%
Разработчик на Spring Framework
-25%
Golang Developer. Professional
-25%
Python Developer. Basic
-25%
iOS Developer. Professional
-25%
Highload Architect
-25%
JavaScript Developer. Basic
-25%
Kotlin Backend Developer
-25%
JavaScript Developer. Professional
-25%
Android Developer. Basic
-25%
Unity Game Developer. Basic
-25%
Разработчик C#
-25%
Программист С Web-разработчик на Python Алгоритмы и структуры данных Framework Laravel PostgreSQL Reverse-Engineering. Professional CI/CD Vue.js разработчик VOIP инженер Программист 1С Flutter Mobile Developer Супер - интенсив по Kubernetes Symfony Framework Advanced Fullstack JavaScript developer Супер-интенсив "Azure для разработчиков"
Инфраструктура
Мониторинг и логирование: Zabbix, Prometheus, ELK
-25%
DevOps практики и инструменты
-25%
Архитектор сетей
-25%
Инфраструктурная платформа на основе Kubernetes
-25%
Супер-интенсив «ELK»
-16%
Супер-интенсив «IaC Ansible»
-16%
Супер-интенсив "SQL для анализа данных"
-16%
Базы данных Сетевой инженер AWS для разработчиков Cloud Solution Architecture Разработчик голосовых ассистентов и чат-ботов Внедрение и работа в DevSecOps Администратор Linux. Виртуализация и кластеризация Нереляционные базы данных Супер-практикум по использованию и настройке GIT IoT-разработчик Супер-интенсив «СУБД в высоконагруженных системах»
Специализации Курсы в разработке Подготовительные курсы
+7 499 938-92-02

Вывод строки в Java: как определить, является ли строка анаграммой?

Java_Deep_24.5_site-5020-ae1869.png

При проведении собеседования на должность «Разработчик Java» технические специалисты любят задавать соискателям различные задачки. Одна из них — как определить, является ли одна строка перестановкой другой в Java. И как это сделать разными способами.

Для начала уточним детали. Во-первых, следует учесть чувствительность к регистру. Например, является ли строка «dog» анаграммой «God». Также необходимо выяснить, учитываются ли пробелы.

Давайте предположим, что регистр и пробелы учитываются, а строки «dog» и « dog» не являются одинаковыми, так как они имеют разную длину. Как бы там ни было, эта задачка в Java совсем несложна и может быть решена несколькими способами.

Метод 1. Сортировка строк

Если строки в Java являются анаграммами, они включают в себя одинаковые символы, которые расположены в разном порядке. Для упорядочивания символов прекрасно подходит сортировка. После её выполнения консоль выведет 2 отсортированные версии строк.

public String sort(String s) {
    char[] content = s.toCharArray();
    java.util.Arrays.sort(content);
    return new String(content);
}

public boolean permutation (String s,String t) {
    if (s.length() != t.length()) {
        return false;
    }
    return sort(s).equals(sort(t));
}

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

Метод 2. Проверяем счётчики идентичных символов

Этот алгоритм работает за счёт использования такого свойства анаграммы, как одинаковые «счётчики» символов. Грубо говоря, мы лишь подсчитываем, сколько раз в нашей строке встречался каждый символ. А после того, как программа выведет результат, просто сравниваем массивы, которые получены для каждой строки.

public boolean permutation(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }

    int[] letters = new int[256];

    char[] s_array = s.toCharArray();
    for (char c : s_array) {
        letters[c]++;
    }

    for (int i = 0; i < t.length(); i++) {
        int c = (int) t.charAt(i);
        if (--letters[c] < 0) {
            return false;
        }
    }

    return true;
}

Обратите внимание, что здесь мы подразумеваем использование набора символов ASCII. Но этот способ можно модернизировать, что позволит нам работать не только через ASCII, но и за один проход цикла:

private static boolean permutations(String input, String second) {
if( input.length() != second.length()){
return false;
}
Map<Character,Integer> map = new HashMap<>();
char[] inArray = input.toCharArray();
char[] secArray = second.toCharArray();
for( int i=0;i<inArray.length;i++ ){
Integer val = map.computeIfAbsent(inArray[i], character -> 0);
val++;
putRemoveMapValue(inArray[i],val,map);

val = map.computeIfAbsent(secArray[i], character -> 0);
val--;
putRemoveMapValue(secArray[i],val,map);
}
return map.size() == 0;
}

private static void putRemoveMapValue(char ch, int val, Map<Character, Integer> map){
if( val == 0 ){
map.remove(ch);
} else {
map.put(ch,val);
}
}

Что же, надеюсь, теперь эта задачка в Java не вызовет у вас затруднений. Но если вы хотите получить действительно продвинутые и систематизированные знания по Java-разработке, записывайтесь на наш курс!

Есть вопрос? Напишите в комментариях!

Не пропустите новые полезные статьи!

Спасибо за подписку!

Мы отправили вам письмо для подтверждения вашего email.
С уважением, OTUS!

Автор
0 комментариев
Для комментирования необходимо авторизоваться
🎁 Максимальная скидка!
Черная пятница уже в OTUS! Скидка -25% на всё!