Метод, определяющий, является ли одна строка перестановкой другой

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

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

Сравнивая две строки, помните, что строки разной длинны не могут быть анаграммами.
Существует два способа решить эту задачу.

Способ 1. Сортировка строк.

Если строки являются анаграммами, то они состоят из одинаковых символов, расположенных в разном порядке. Сортировка двух строк должна упорядочить символы. Теперь остается только сравнить две отсортированные версии строк.

			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));
}
		

Хотя этот алгоритм нельзя назвать оптимальным во всех смыслах, он удачен, поскольку его легко понять. С практической точки зрения это превосходный способ решить задачу. Однако если важна эффективность, нужно реализовывать другой вариант алгоритма.

Способ 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;
}
		

Обратите внимание на строку 6. В данной реализации мы подразумеваем, что используется набор символов ASCII, но алфавит может быть разным.

Разбор взят из перевода книги Г. Лакман Макдауэлл и предназначен исключительно для ознакомления.Если он вам понравился, то рекомендуем купить книгу «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию».