Ellenőrizze, hogy két karakter-e Anagramm a Java-ban

1. Áttekintés

A Wikipedia szerint az anagramma egy szó vagy kifejezés, amelyet egy másik szó vagy kifejezés betűinek átrendezésével hoztak létre.

Ezt általánosíthatjuk a string feldolgozásban azzal, hogy ezt mondjuk egy karakterlánc anagramma egy másik karakterlánc, amely pontosan ugyanannyi mennyiségű karaktert tartalmaz, tetszőleges sorrendben.

Ebben az oktatóanyagban az egész karakterlánc-anagrammák felderítését fogjuk megvizsgálni, ahol az egyes karakterek mennyiségének egyenlőnek kell lennie, beleértve a nem alfa karaktereket, például a szóközöket és a számjegyeket. Például, „! Alacsony sótartalmú!” és „Baglyok-lat !!” anagrammának tekintenék, mivel pontosan ugyanazokat a karaktereket tartalmazzák.

2. Megoldás

Hasonlítsunk össze néhány megoldást, amelyek eldönthetik, hogy két karakterlánc anagramma-e. Mindegyik megoldás az elején ellenőrzi, hogy a két karakterlánc azonos karakterekkel rendelkezik-e. Ez azóta gyors módja a korai kilépésnek a különböző hosszúságú bemenetek nem lehetnek anagrammák.

Minden lehetséges megoldásnál nézzük meg a megvalósítás összetettségét nekünk, mint fejlesztőknek. Megvizsgáljuk a CPU időbeli összetettségét is, nagy O jelöléssel.

3. Ellenőrizze rendezés szerint

Minden karakterlánc karakterét átrendezhetjük a karakterek rendezésével, amely két normalizált karaktertömböt eredményez.

Ha két húr anagramm, akkor normalizált formájuknak meg kell egyeznie.

A Java-ban először a két karakterláncot konvertálhatjuk char [] tömbök. Ezután rendezhetjük ezt a két tömböt és ellenőrizhetjük az egyenlőséget:

logikai isAnagramSort (String string1, String string2) {if (string1.length ()! = string2.length ()) {return false; } char [] a1 = string1.toCharArray (); char [] a2 = string2.toCharArray (); Tömbök.rendezés (a1); Tömbök.rendezés (a2); visszatérő tömbök.egyenlő (a1, a2); } 

Ez a megoldás könnyen érthető és megvalósítható. Ennek az algoritmusnak a teljes futási ideje azonban O (n log n) mert egy tömb rendezése n karakter vesz O (n log n) idő.

Az algoritmus működése érdekében mindkét bemeneti karakterláncról másolatot kell készítenie karaktertömbökként, egy kis plusz memória felhasználásával.

4. Ellenőrizze számlálással

Alternatív stratégia az, ha a bemeneteinkben megszámoljuk az egyes karakterek előfordulásait. Ha ezek a hisztogramok megegyeznek a bemenetek között, akkor a húrok anagrammák.

Egy kis memória megtakarításához csak egy hisztogramot készítsünk. Az első karaktersorozatban növeljük az egyes karakterek számát, a másodikban pedig az egyes karakterek számát. Ha a két húr anagramma, akkor az eredmény az lesz, hogy minden 0-ra egyensúlyoz.

A hisztogramhoz rögzített méretű táblázatokra van szükség, amelyek méretét a karakterkészlet mérete határozza meg. Például, ha csak egy bájtot használunk minden karakter tárolásához, akkor 256-os számlálótömböt használhatunk az egyes karakterek előfordulásának számításához:

privát statikus int CHARACTER_RANGE = 256; nyilvános logikai isAnagramCounting (String string1, String string2) {if (string1.length ()! = string2.length ()) {return false; } int count [] = új int [CHARACTER_RANGE]; for (int i = 0; i <string1.length (); i ++) {count [string1.charAt (i)] ++; gróf [string2.charAt (i)] -; } for (int i = 0; i <CHARACTER_RANGE; i ++) {if (count [i]! = 0) {return false; }} return true; }

Ez a megoldás gyorsabb az idő összetettségével Tovább). Ehhez azonban további helyre van szüksége a számláló tömbhöz. 256 egész számnál az ASCII esetében ez nem túl rossz.

Ha azonban növelnünk kell CHARACTER_RANGE a több bájtos karakterkészletek, például az UTF-8 támogatásához ez nagyon emlékezetessé válna. Ezért csak akkor praktikus, ha a lehetséges karakterek száma kis tartományban van.

Fejlesztési szempontból ez a megoldás több kódot tartalmaz a karbantartáshoz, és kevésbé használja ki a Java könyvtár funkcióit.

5. Ellenőrizze MultiSet

Használatával egyszerűsíthetjük a számlálási és összehasonlítási folyamatot MultiSet. MultiSet olyan gyűjtemény, amely duplikált elemekkel támogatja a megrendelésektől független egyenlőséget. Például az {a, a, b} és a {a, b, a} többkészlet egyenlő.

Használni Multiset, először hozzá kell adnunk a Guava-függőséget a projektünkhöz pom.xml fájl:

 com.google.guava guava 28.1-jre 

Minden bemeneti karakterláncunkat a-vá konvertáljuk MultiSet karakterek. Akkor ellenőrizzük, hogy egyenlőek-e:

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

Ez az algoritmus megoldja a problémát Tovább) időt anélkül, hogy nagy számláló tömböt kellene deklarálnunk.

Hasonló az előző számlálási megoldáshoz. Azonban ahelyett, hogy fix méretű táblázatot használnánk a számláláshoz, kihasználjuk a MutlitSet osztály egy változó méretű tábla szimulálásához, az egyes karakterek számával.

Ennek a megoldásnak a kódja jobban kihasználja a magas szintű könyvtári képességeket, mint a számlálási megoldásunk.

6. Levél alapú Anagram

Az eddigi példák nem tartják be szigorúan az anagramma nyelvi meghatározását. Ennek oka az, hogy az írásjeleket az anagramma részének tekintik, és a kis- és nagybetűket érzékenyek.

Alkalmazzuk az algoritmusokat egy betűalapú anagramma engedélyezéséhez. Vegyük csak figyelembe a kis- és nagybetűk nélküli betűk átrendezését, függetlenül más karakterektől, például a szóközöktől és az írásjelektől. Például, „Tizedesjegy” és "Pont vagyok a helyén." anagrammái lennének egymásnak.

A probléma megoldása érdekében először a két beviteli karakterláncot előzetesen feldolgozhatjuk a nem kívánt karakterek kiszűrésére és a betűk kisbetűkké alakítására. Akkor használhatjuk a fenti megoldások egyikét (mondjuk a MultiSet megoldás) a feldolgozott húrok anagrammáinak ellenőrzéséhez:

Karakterlánc-előfeldolgozás (karakterlánc-forrás) {return source.replaceAll ("[^ a-zA-Z]", "") .toLowerCase (); } logikai isLetterBasedAnagramMultiset (String string1, String string2) {return isAnagramMultiset (preprocess (string1), preprocess (string2)); }

Ez a megközelítés általános módszer lehet az anagramma problémák összes változatának megoldására. Például, ha számjegyeket is szeretnénk felvenni, akkor csak az előfeldolgozó szűrőt kell beállítanunk.

7. Következtetés

Ebben a cikkben három algoritmust vizsgáltunk annak ellenőrzésére, hogy egy adott karakterlánc egy másik, annak karakter-e anagramma. Minden megoldásnál megvitattuk a kompromisszumokat a szükséges memória sebessége, olvashatósága és mérete között.

Megvizsgáltuk azt is, hogyan lehet az algoritmusokat adaptálni az anagrammák ellenőrzésére a hagyományosabb nyelvi értelemben. Ezt úgy értük el, hogy a bemeneteket kisbetűkkel előre feldolgoztuk.

Mint mindig, a cikk forráskódja elérhető a GitHubon.