Вывод строки в Java: как определить, является ли строка анаграммой? | OTUS
⚡ Подписка на курсы OTUS!
Интенсивная прокачка навыков для IT-специалистов!
Подробнее

Курсы

Программирование
iOS Developer. Professional Kotlin Backend Developer Flutter Mobile Developer Symfony Framework C++ Developer. Basic Unity Game Developer. Basic Java Developer. Professional
-35%
Highload Architect Unity Game Developer. Professional React.js Developer Специализация Java-разработчик
-25%
Алгоритмы и структуры данных
-16%
Scala-разработчик C# Developer. Professional
-23%
Разработчик голосовых ассистентов и чат-ботов Team Lead Архитектура и шаблоны проектирования NoSQL Web-разработчик на Python Golang Developer. Professional PostgreSQL Vue.js разработчик Супер-практикум по использованию и настройке GIT Разработчик IoT Подготовка к сертификации Oracle Java Programmer (OCAJP) Программист С HTML/CSS
Инфраструктура
Инфраструктурная платформа на основе Kubernetes Microservice Architecture Базы данных Highload Architect Reverse-Engineering. Professional
-8%
Network engineer. Basic Administrator Linux.Basic MongoDB Infrastructure as a code MS SQL Server Developer Cloud Solution Architecture Мониторинг и логирование: Zabbix, Prometheus, ELK Супер-практикум по использованию и настройке GIT Разработчик IoT Экcпресс-курс «ELK» Супер-интенсив "Tarantool" Экспресс-курс «CI/CD или Непрерывная поставка с Docker и Kubernetes» Экспресс-курс «Введение в непрерывную поставку на базе Docker»
Корпоративные курсы
Безопасность веб-приложений Экосистема Hadoop, Spark, Hive Пентест. Практика тестирования на проникновение Node.js Developer Java QA Engineer. Basic
-18%
Reverse-Engineering. Professional
-8%
DevOps практики и инструменты NoSQL Reverse-Engineering. Basic Cloud Solution Architecture Внедрение и работа в DevSecOps Супер-практикум по работе с протоколом BGP Game QA Engineer Супер - интенсив по Kubernetes Дизайн сетей ЦОД Экспресс-курс «IaC Ansible» Экспресс-курс по управлению миграциями (DBVC) Экспресс-курс "Версионирование и командная работа с помощью Git" Основы Windows Server
Специализации Курсы в разработке Подготовительные курсы Подписка
+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 комментариев
Для комментирования необходимо авторизоваться