Provjerite jesu li dva niza anagrami na Javi

1. Pregled

Prema Wikipediji, anagram je riječ ili fraza nastala preslagivanjem slova druge riječi ili fraze.

To možemo generalizirati u obradi niza govoreći to anagram niza je drugi niz s točno jednakom količinom svakog znaka u bilo kojem redoslijedu.

U ovom ćemo uputstvu razmotriti otkrivanje cijelih anagrama niza gdje količina svakog znaka mora biti jednaka, uključujući ne-alfa znakove poput razmaka i znamenki. Na primjer, "! S malo soli!" i "Sove-lat !!" smatrali bi se anagramima jer sadrže potpuno iste znakove.

2. Rješenje

Usporedimo nekoliko rješenja koja mogu odlučiti jesu li dva niza anagrami. Svako rješenje na početku će provjeriti imaju li dva niza jednak broj znakova. Ovo je brzi način za rani izlazak od ulazi različitih duljina ne mogu biti anagrami.

Za svako moguće rješenje, pogledajmo složenost implementacije za nas kao programere. Također ćemo pogledati vremensku složenost CPU-a, koristeći veliku O oznaku.

3. Provjerite sortiranjem

Znakove svakog niza možemo preurediti sortiranjem njihovih znakova, što će stvoriti dva normalizirana niza znakova.

Ako su dva niza anagrami, njihovi normalizirani oblici trebali bi biti jednaki.

U Javi možemo prvo pretvoriti dva niza u char [] nizovi. Tada možemo sortirati ova dva niza i provjeriti jednakost:

boolean isAnagramSort (Niz string1, Niz string2) {if (string1.length ()! = string2.length ()) {return false; } char [] a1 = string1.toCharArray (); char [] a2 = string2.toCharArray (); Nizovi.sort (a1); Nizovi.sort (a2); return Nizovi.equals (a1, a2); } 

Ovo je rješenje lako razumjeti i primijeniti. Međutim, ukupno vrijeme rada ovog algoritma je O (n zapisnik n) jer sortiranje niza od n likova traje O (n zapisnik n) vrijeme.

Da bi algoritam mogao funkcionirati, mora napraviti kopiju oba ulazna niza kao nizove znakova, koristeći malo dodatne memorije.

4. Provjera brojanjem

Alternativna strategija je brojanje broja pojavljivanja svakog znaka u našim ulazima. Ako su ovi histogrami jednaki između ulaza, tada su nizovi anagrami.

Da bismo uštedjeli malo memorije, napravimo samo jedan histogram. Povećat ćemo broj za svaki znak u prvom nizu, a smanjiti za svaki znak u drugom. Ako su dva niza anagrami, rezultat će biti da se sve uravnoteži na 0.

Histogramu je potrebna tablica brojeva fiksne veličine s veličinom definiranom veličinom skupa znakova. Na primjer, ako za pohranu svakog znaka koristimo samo jedan bajt, tada možemo koristiti veličinu polja za brojanje 256 za brojanje pojavljivanja svakog znaka:

privatni statički int CHARACTER_RANGE = 256; javna boolean isAnagramCounting (Niz string1, Niz string2) {if (string1.length ()! = string2.length ()) {return false; } int count [] = novi 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; }

Ovo je rješenje brže s vremenskom složenošću Na). Međutim, potreban mu je dodatni prostor za niz za brojanje. Sa 256 cijelih brojeva, za ASCII to nije loše.

Međutim, ako trebamo povećati CHARACTER_RANGE za podršku višebajtnih skupova znakova kao što je UTF-8, ovo bi postalo jako gladno memorije. Stoga je stvarno praktično samo kad je broj mogućih znakova u malom rasponu.

S razvojnog gledišta, ovo rješenje sadrži više koda za održavanje i manje koristi funkcije Java knjižnice.

5. Provjerite s MultiSet

Pomoću toga možemo pojednostaviti postupak brojanja i usporedbe MultiSet. MultiSet je zbirka koja podržava jednakost neovisnu o redoslijedu s dupliciranim elementima. Na primjer, multiskupovi {a, a, b} i {a, b, a} jednaki su.

Koristiti Multiset, prvo moramo dodati ovisnost o Guavi u naš projekt pom.xml datoteka:

 com.google.guava guava 28,1-jre 

Pretvorit ćemo svaki naš ulazni niz u MultiSet likova. Zatim ćemo provjeriti jesu li jednake:

boolean isAnagramMultiset (Niz string1, Niz 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); } 

Ovaj algoritam rješava problem u Na) vrijeme bez potrebe za deklariranjem velikog polja za brojanje.

Slično je prethodnom rješenju brojanja. Međutim, umjesto da za brojanje koristimo tablicu fiksne veličine, mi koristimo MutlitSet klasa za simulaciju tablice promjenljive veličine, s brojem za svaki znak.

Kôd za ovo rješenje više koristi mogućnosti knjižnice na visokoj razini od našeg rješenja za brojanje.

6. Anagram zasnovan na slovima

Dosadašnji se primjeri ne pridržavaju strogo lingvističke definicije anagrama. To je zato što interpunkcijske znakove smatraju dijelom anagrama i razlikuju velika i mala slova.

Prilagodimo algoritme kako bismo omogućili anagram zasnovan na slovima. Razmotrimo samo preslagivanje slova koja ne razlikuju velika i mala slova, bez obzira na ostale znakove, poput razmaka i interpunkcije. Na primjer, "Decimalna točka" i "Ja sam točka na mjestu." bili bi anagrami jedno drugoga.

Da bismo riješili taj problem, prvo možemo obraditi dva ulazna niza kako bismo filtrirali neželjene znakove i pretvorili slova u mala slova. Tada možemo koristiti jedno od gornjih rješenja (recimo, MultiSet rješenje) za provjeru anagrama na obrađenim nizovima:

Predobrada niza (izvor niza) {return source.replaceAll ("[^ a-zA-Z]", "") .toLowerCase (); } boolean isLetterBasedAnagramMultiset (String string1, String string2) {return isAnagramMultiset (pretproces (string1), pretproces (string2)); }

Ovaj pristup može biti općeniti način rješavanja svih varijanti problema s anagramima. Na primjer, ako također želimo uključiti znamenke, samo trebamo podesiti filtar za predobradu.

7. Zaključak

U ovom smo članku pogledali tri algoritma za provjeru je li zadani niz anagram drugog znaka za znak. Za svako rješenje razgovarali smo o kompromisima između brzine, čitljivosti i veličine potrebne memorije.

Također smo pogledali kako prilagoditi algoritme za provjeru anagrama u tradicionalnijem lingvističkom smislu. To smo postigli predobradom unosa malim slovima.

Kao i uvijek, izvorni kôd članka dostupan je na GitHubu.