Anagrams

Hooray! Ez a cikk az utolsó stringmanipulációs feladat a tanfolyam ezen szakaszában. Hosszú utat tettünk meg!

Ebben a kihívásban az anagrammák JavaScriptben történő felismerésének két módját vizsgáljuk meg.

Mi az anagramma?

Egy szót akkor nevezünk egy másik szó anagrammájának, ha a másik szó betűinek átrendezésével, minden betűt csak egyszer felhasználva alkotható meg. Pl. a listen a silent anagrammája.

Lássunk hozzá, rendben?

Már be kell állítanod a fejlesztőkörnyezetedet ehhez a tanfolyamhoz. Frissítsd a klónozott tárolódat a git pull parancs futtatásával. A Beginner mappán belül navigálj az isAnagram mappába. Az ehhez a kihíváshoz szükséges munkánkat itt fogjuk elvégezni. Győződjünk meg róla, hogy követjük azindex-START.js fájlt.

A kihívás

Adott két karakterlánc, írj egy algoritmust annak ellenőrzésére, hogy azok egymás anagrammái-e. Adjon vissza igazat, ha átmennek a teszten, és hamisat, ha nem. Pl

isAnagram('silent', 'listen') // should return true

Algoritmikus gondolkodás

A kihívás megoldásához írunk egy függvényt, amely két paramétert fogad el, azaz a két összehasonlítandó karakterláncot.

BeginnerTailwind.com Learn Tailwind CSS from Scratch

A függvényben összehasonlítjuk a két szót, hogy tartalmaznak-e ugyanannyiszor használt azonos karaktereket. A hibák elkerülése érdekében szanáljuk a karakterláncot, így megszabadulunk a nem kívánt karakterektől és szóközöktől, mivel ezek nem az ábécé betűi.

Az összehasonlítások elvégzése előtt minden karaktert közös nagybetűsre alakítunk, hogy elkerüljük az eltérő nagybetűs írásmód miatti hibákat. Annak ellenőrzése, hogy mindkét szó azonos hosszúságú-e, szintén nagyon fontos, mivel ez az érvényes összehasonlítás elsődleges tényezője.

Végezzük el ezt.

Kódmegvalósítás

A következőkben a fenti algoritmikus logikánkat követve kétféleképpen fogjuk megvizsgálni a megoldásunk megvalósítását. Ezek a következők:

• Közvetlen összehasonlítás
• Karaktertérképes összehasonlítás

Közvetlen összehasonlítás

Ebben a megközelítésben definiálunk egy függvényt, amely két paramétert fogad el, azaz a két összehasonlítandó karakterláncot. Ezután mindkét karakterláncot megtisztítjuk, hogy biztosítsuk, hogy csak betűket és közös esetet hasonlítunk össze.

A karakterlánc tisztításaA karakterlánc tisztításához létrehozunk egy sanitizeString függvényt. Ez a függvény paraméterként elfogadja a tisztítandó karakterláncot, és a .toLowerCase(), .replace(), .split(), .sort() és .join() metódusokat használja a karakterlánc manipulálására az alábbiak szerint:

const sanitizeString = function (str) { return str.toLowerCase().replace(//g, '').split('').sort().join('');}

Bontjuk le egy kicsit a dolgokat:

• Először a teljes karakterláncot kisbetűvé alakítjuk a .toLowerCase() metódus segítségével.
• Ezután a .replace() módszerrel átkutatjuk a karakterláncot a megadott reguláris kifejezésmintával, és minden nem ábécés karaktert üres karakterlánccal helyettesítünk. Így csak a betűket hagyjuk meg. Se szóközök, se szimbólumok!
• A következő lépésben meghívjuk a .split() metódust, hogy a karakterláncot karaktertömbre osszuk.
• A .sort() metódus segítségével a betűket (elemeket) a tömbön belül ábécérendbe rendezzük.
• Végül pedig a most már ábécérendbe rendezett betűtömböt újra összeillesztjük, hogy ismét egy karakterláncot alkossunk.

Ezt a stringet adjuk vissza szanált stringként.

Sima ügy!** Ugye?**

A szanált stringek összehasonlításaA string fentiek szerinti szanálása talán a megoldás legtrükkösebb része. Ezután egyszerűen megtisztítjuk a kapott karakterláncokat a sanitizeString függvény segítségével, és összehasonlítjuk az eredményeket. Ha mindkét karakterlánc egyezik, akkor true-t adunk vissza, jelezve, hogy anagrammaként mennek át. Ha nem egyeznek, akkor false-t adunk vissza, jelezve, hogy nem azok.

A teljes megoldás alább látható:

function isAnagram(stringA, stringB) { const sanitizeString = function (str) { return str.toLowerCase().replace(//g, '').split('').sort().join(''); } return sanitizeString(stringA) == sanitizeString(stringB)}

Egyet le!** Legyünk furcsábbak! 😈**

Amint látni fogod, az a megközelítés, amit most megvizsgálunk, egy több lépésből álló eljárást követ a probléma megoldásához.

Karaktertérkép összehasonlítás

Ebben a megközelítésben először egy karaktertérképet generálunk a createCharMap függvényünkkel.

Mi az a karaktertérkép?

Az ebben a kontextusban használt , a karaktertérkép objektum egy olyan objektum, amely egy karakterlánc minden karakterét hozzárendeli ahhoz, hogy hányszor fordul elő a karakterláncban.

A karaktertérkép létrehozásaAz alábbi createCharMap függvényünkben egy for…of ciklus segítségével végigmegyünk a kapott karakterlánc minden egyes karakterén.

function createCharMap(text) { let charMap = {} for (let char of text) { if (charMap.hasOwnProperty(char)) { charMap++ } else { charMap = 1 } } return charMap}

Minden karakter esetében ellenőrizzük, hogy a karakter létezik-e már a karaktertérkép charMap tulajdonságaként a .hasOwnProperty() módszerrel. Ha igen, akkor növeljük az értékét, ha nem, akkor hozzáadjuk a karaktert tulajdonságként, és értékét 1-re állítjuk.

A végén visszaadjuk a charMap-et, ami a karaktertérkép objektum.

Karaktertérképek összehasonlításaMost, hogy már van módunk a karaktertérképek létrehozására, a következő lépés a két karakterlánc karaktertérképének összehasonlítása lesz, ahogy az alábbi teljes megoldás mutatja:

function isAnagram(stringA, stringB) { function createCharMap(text) { let charMap = {} for (let char of text) { if (charMap.hasOwnProperty(char)) { charMap++ } else { charMap = 1 } } return charMap } if (stringA.length === stringB.length) { let stringAMap = createCharMap(stringA) let stringBMap = createCharMap(stringB) for (let char in stringAMap) { if (stringAMap !== stringBMap) { return false } } return true } else { return false }}

Megjegyezzük, hogy először azt ellenőrizzük, hogy a két karakterlánc hossza megegyezik-e egymással. Ha nem, akkor false adjuk vissza, mivel ez azt jelzi, hogy soha nem lehetnek anagrammák. Ha viszont igen, akkor továbbmegyünk, és létrehozzuk a stringAMap és stringBMap változókban tárolt karaktertérképüket.

A következő lépésben a for…in ciklus segítségével összehasonlítunk minden egyes karaktert és értéket a stringAMap-ben a stringBMap-ben lévő karakter megfelelő értékével. Ha valamelyik érték nem egyezik, akkor false-t adunk vissza annak jeleként, hogy a karakterláncok nem anagrammák. Ha azonban minden érték egyezik, a tesztet sikeresen elvégeztük, és true-t adunk vissza annak jeleként, hogy a vizsgált karakterláncok valóban anagrammák.

Megcsináltuk. Valóban hosszabb megvalósítás, de mindenképpen magyarázhatóbb.

Futtassuk most a tesztjeinket, jó?

Helyesség tesztelése Jesttel

A fenti megoldások mindegyikének teszteléséhez futtassuk a következő parancsot a terminálról:

npm run test isAnagram

• Közvetlen összehasonlítás

• Karaktertérkép összehasonlítás

Úgy tűnik, mindig jól csináljuk! Minden tesztet teljesítettünk.

Teljesítménytesztelés JSPerf-fel

Itt egy teljesítménytesztet futtatunk, hogy megállapítsuk, melyik megoldás a gyorsabb. Az alábbiakban egy képernyőképet találunk az eredményről:

Az eredményből megfigyelhetjük, hogy:

A gyorsabb megvalósítás a Karaktertérkép-összehasonlító megközelítés és a Közvetlen összehasonlítás módszer, bár tömören körülbelül 52%-kal lassabb.

**Meglepő, nem igaz? A mérőszámok azonban sosem hazudnak!**

Gyakorlati alkalmazás

A fentebb vizsgált algoritmusok többféleképpen alkalmazhatók. Ezek közé tartoznak:

• Titkosítás
• Jelszógenerálás
• Bizalmas időbélyegzés
• Interjúk kódolása
• Mnemotechnika generálása
• Szójátékok
  

  Következtetés

A fentebb vizsgált technikákat és fogalmakat figyelembe véve, értékes módszereket tanultunk meg a karakterláncok manipulálására annak megállapítása érdekében, hogy azok anagrammák-e. Különböző területeket is feltártunk, ahol ez a tudás közvetlenül hasznosítható.

Teljesítménytesztjeink lefuttatása után most már megállapíthatjuk, hogy a probléma megoldásának legoptimálisabb megközelítése a karaktertérkép-összehasonlító módszer.

További olvasnivaló

A fentebb kiemelt fogalmak és technikák megismeréséhez a következő linkeket használhatja:

• Reguláris kifejezések
• .replace()
• .split()
• .sort()
• .join()
• .hasOwnProperty()
• For…of vs for…in loop

Viszlát a következő, tömbkezelő algoritmusokra koncentráló cikkekben!✌🏿

Tetszett a cikk? Kövesd a @worldclassdev-et a Twitteren