Проверете дали два низа са анаграми в Java

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 файл:

 com.google.guava guava 28.1-jre  

Ще преобразуваме всеки от нашите входни низове в MultiSet символи. След това ще проверим дали са равни:

boolean isAnagramMultiset(String string1, String string2) { if (string1.length() != string2.length()) { return false; } Multiset multiset1 = HashMultiset.create(); Multiset 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.