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

При проведении собеседования на должность «Разработчик 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-разработке, записывайтесь на наш курс!