1. Обзор
Согласно Википедии , анаграмма — это слово или фраза, образованная перестановкой букв другого слова или фразы.
Мы можем обобщить это при обработке строк, сказав, что анаграмма строки — это другая строка с точно таким же количеством каждого символа в ней в любом порядке .
В этом уроке мы рассмотрим обнаружение анаграмм целых строк, в которых количество всех символов должно быть равным, включая не-альфа-символы, такие как пробелы и цифры. Например, «!с низким содержанием соли!» и «совы-лат!!» будут считаться анаграммами, поскольку они содержат точно такие же символы.
2. Решение
Давайте сравним несколько решений, которые могут решить, являются ли две строки анаграммами. Каждое решение будет проверять в начале, имеют ли две строки одинаковое количество символов. Это быстрый способ выйти раньше, поскольку входные данные разной длины не могут быть анаграммами .
Для каждого возможного решения давайте посмотрим на сложность реализации для нас как разработчиков. Мы также рассмотрим временную сложность для процессора, используя нотацию большого O.
3. Проверка путем сортировки
Мы можем переставить символы каждой строки, отсортировав их символы, что создаст два нормализованных массива символов.
Если две строки являются анаграммами, их нормализованные формы должны быть одинаковыми.
В Java мы можем сначала преобразовать две строки в массивы char[] . Затем мы можем отсортировать эти два массива и проверить на равенство:
boolean isAnagramSort(String string1, String string2) {
if (string1.length() != string2.length()) {
return false;
}
char[] a1 = string1.toCharArray();
char[] a2 = string2.toCharArray();
Arrays.sort(a1);
Arrays.sort(a2);
return Arrays.equals(a1, a2);
}
Это решение легко понять и реализовать. Однако общее время работы этого алгоритма равно O(n log n) , потому что сортировка массива из n символов занимает время O(n log n) .
Чтобы алгоритм работал, он должен сделать копию обеих входных строк в виде массивов символов, используя немного дополнительной памяти.
4. Проверяйте, считая
Альтернативная стратегия состоит в том, чтобы подсчитать количество вхождений каждого символа в наши входные данные. Если эти гистограммы равны между входными данными, то строки являются анаграммами.
Для экономии памяти построим только одну гистограмму. Мы будем увеличивать счетчик для каждого символа в первой строке и уменьшать счетчик для каждого символа во второй. Если две строки являются анаграммами, то в результате все уравновесится до 0.
Для гистограммы требуется таблица счетчиков фиксированного размера, размер которой определяется размером набора символов. Например, если мы используем только один байт для хранения каждого символа, то мы можем использовать размер массива подсчета 256 для подсчета появления каждого символа:
private static int CHARACTER_RANGE= 256;
public boolean isAnagramCounting(String string1, String string2) {
if (string1.length() != string2.length()) {
return false;
}
int count[] = new int[CHARACTER_RANGE];
for (int i = 0; i < string1.length(); i++) {
count[string1.charAt(i)]++;
count[string2.charAt(i)]--;
}
for (int i = 0; i < CHARACTER_RANGE; i++) {
if (count[i] != 0) {
return false;
}
}
return true;
}
Это решение быстрее с временной сложностью O(n) . Однако для массива подсчета требуется дополнительное пространство. При 256 целых числах для ASCII это не так уж плохо.
Однако, если нам нужно увеличить CHARACTER_RANGE для поддержки многобайтовых наборов символов, таких как UTF-8, это станет очень жадным до памяти. Следовательно, это действительно практично только тогда, когда количество возможных символов находится в небольшом диапазоне.
С точки зрения разработки это решение содержит больше кода, который необходимо поддерживать, и меньше использует функции библиотеки Java.
5. Проверьте с помощью MultiSet
Мы можем упростить процесс подсчета и сравнения, используя MultiSet . MultiSet — это коллекция, которая поддерживает независимое от порядка равенство с повторяющимися элементами. Например, мультимножества {a, a, b} и {a, b, a} равны.
Чтобы использовать Multiset , нам сначала нужно добавить зависимость Guava в файл нашего проекта pom.xml :
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>31.0.1-jre</version>
</dependency>
Мы преобразуем каждую из наших входных строк в MultiSet символов. Затем мы проверим, равны ли они:
boolean isAnagramMultiset(String string1, String string2) {
if (string1.length() != string2.length()) {
return false;
}
Multiset<Character> multiset1 = HashMultiset.create();
Multiset<Character> multiset2 = HashMultiset.create();
for (int i = 0; i < string1.length(); i++) {
multiset1.add(string1.charAt(i));
multiset2.add(string2.charAt(i));
}
return multiset1.equals(multiset2);
}
Этот алгоритм решает задачу за время O(n) без необходимости объявления большого массива счетчиков.
Это похоже на предыдущее решение для подсчета. Однако вместо использования таблицы фиксированного размера для подсчета мы используем класс MutlitSet для имитации таблицы переменного размера с подсчетом для каждого символа.
Код для этого решения больше использует возможности библиотеки высокого уровня, чем наше решение для подсчета.
6. Буквенная анаграмма
Примеры до сих пор не строго придерживаются лингвистического определения анаграммы. Это потому, что они считают знаки препинания частью анаграммы и чувствительны к регистру.
Давайте адаптируем алгоритмы, чтобы включить анаграмму на основе букв. Давайте рассмотрим только перестановку букв без учета регистра, независимо от других символов, таких как пробелы и знаки препинания. Например, «десятичная точка» и «я точка на месте». были бы анаграммами друг друга.
Чтобы решить эту проблему, мы можем сначала предварительно обработать две входные строки, чтобы отфильтровать нежелательные символы и преобразовать буквы в буквы нижнего регистра. Затем мы можем использовать одно из приведенных выше решений (скажем, решение MultiSet ) для проверки анаграмм в обработанных строках:
String preprocess(String source) {
return source.replaceAll("[^a-zA-Z]", "").toLowerCase();
}
boolean isLetterBasedAnagramMultiset(String string1, String string2) {
return isAnagramMultiset(preprocess(string1), preprocess(string2));
}
Такой подход может быть общим способом решения всех вариантов задач на анаграммы. Например, если мы также хотим включить цифры, нам просто нужно настроить фильтр предварительной обработки.
7. Заключение
В этой статье мы рассмотрели три алгоритма проверки того, является ли данная строка анаграммой другой, символ за символом. Для каждого решения мы обсудили компромиссы между скоростью, удобочитаемостью и объемом требуемой памяти.
Мы также рассмотрели, как адаптировать алгоритмы для проверки анаграмм в более традиционном лингвистическом смысле. Мы достигли этого путем предварительной обработки входных данных в строчные буквы.
Как всегда, исходный код статьи доступен на GitHub .