Anagrammit

Hooray! Tämä artikkeli on viimeinen merkkijonojen manipulointitehtävä tämän kurssin tässä osassa. Olemme kulkeneet pitkän matkan!

Tässä haasteessa tarkastelemme kahta tapaa havaita anagrammeja JavaScriptissä.

Mikä on anagrammi?

Sanan sanotaan olevan toisen sanan anagrammi, kun se voidaan muodostaa järjestelemällä toisen sanan kirjaimet uudelleen käyttäen jokaista kirjainta vain kerran. Esim. kuuntele on anagrammi sanasta silent.

Lähdetäänkö hommiin?

Sinulla pitäisi jo olla kehitysympäristö valmiina tätä kurssia varten. Päivitä kloonattu arkistosi ajamalla komento git pull. Siirry Beginner-kansion sisällä isAnagram-kansioon. Tämän haasteen työmme tehdään täällä. Varmista, että seuraat mukanaindex-START.js-tiedostoa.

Haaste

Kirjoita kahdelle merkkijonolle algoritmi, joka tarkistaa, ovatko ne toistensa anagrammeja. Palauta true, jos ne läpäisevät testin ja false, jos ne eivät läpäise. Esim

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

Algoritminen ajattelu

Tämän haasteen ratkaisemiseksi kirjoitetaan funktio, joka ottaa vastaan kaksi parametria eli kaksi verrattavaa merkkijonoa.

BeginnerTailwind.com Opi Tailwind CSS:ää alusta alkaen

Funktiossa verrataan kumpaakin sanaa, jotta nähdään, sisältävätkö ne samoja merkkejä, joita käytetään yhtä monta kertaa. Virheiden välttämiseksi puhdistamme merkkijonon, jolloin pääsemme eroon ei-toivotuista merkeistä ja välilyönneistä, koska ne eivät ole aakkosten kirjaimia.

Muunnamme myös kaikki merkit yleiseen kirjainkokoonpanoon ennen vertailujen suorittamista, jotta vältetään vaihtelevasta isojen kirjainten kirjoittamisesta johtuvat virheet. Sen tarkistaminen, että molemmat sanat ovat samanpituisia, on myös hyvin tärkeää, sillä se on ensisijainen tekijä kelvollisen vertailun kannalta.

Tehdään tämä.

Koodin toteutus

Harkitsemme nyt kahta tapaa toteuttaa ratkaisumme edellä esitetyn algoritmisen logiikkamme mukaisesti. Ne ovat:

• Suora vertailu
• Character Map Comparison

Suora vertailu

Tässä lähestymistavassa määrittelemme funktion, joka hyväksyy kaksi parametria eli kaksi vertailtavaa merkkijonoa. Sen jälkeen siirrymme puhdistamaan molemmat merkkijonot varmistaaksemme, että vertaamme vain kirjaimia ja yhteisessä iskussa.

Ohjejonon puhdistaminenOhjejonon puhdistamiseksi luomme funktion sanitizeString. Tämä funktio ottaa parametriksi puhdistettavan merkkijonon ja käyttää metodeja .toLowerCase(), .replace(), .split(), .sort() ja .join() merkkijonon käsittelyyn alla esitetyllä tavalla:

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

Kerrataanpa asioita hieman alemmas:

• Ensin muutamme koko merkkijonon pieneksi metodilla .toLowerCase().
• Seuraavaksi käytämme .replace()-metodia merkkijonon läpikäymiseen määritetyn säännöllisen lausekkeen mallin avulla ja korvaamme jokaisen muun kuin aakkosellisen merkin tyhjällä merkkijonolla. Näin jäljelle jäävät vain kirjaimet. Ei välilyöntejä, ei symboleja!
• Seuraavaksi kutsumme .split():n jakamaan merkkijonon merkkijonomassaksi.
• Metodin .sort() avulla lajittelemme kirjaimet (elementit) massan sisällä aakkosjärjestykseen.
• Viimeiseksi yhdistämme nyt aakkosjärjestykseen järjestetyn kirjainmassan takaisin toisiinsa muodostaaksemme jälleen merkkijonon.

Tämä merkkijono on se, minkä palautamme sanitoituna merkkijonona.

Pehmeää!** Eikö?**

Sanitoitujen merkkijonojen vertailuSanitoidun merkkijonon sanitointi edellä esitetyllä tavalla on ehkä tämän ratkaisun hankalin osa. Seuraavaksi yksinkertaisesti puhdistamme saadut merkkijonot sanitizeString-funktiolla ja vertaamme tuloksia. Jos molemmat merkkijonot täsmäävät, palautamme true merkiksi siitä, että ne ovat anagrammeja. Jos ne eivät täsmää, palautamme false merkiksi siitä, että ne eivät ole.

Katsokaa koko ratkaisu alta:

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

Ensimmäinen suoritettu!** Tehdään vielä oudompaa! 😈**

Kuten huomaat, nyt tarkastelemamme lähestymistapa noudattaa vaiheittaisempaa menettelyä ongelman ratkaisemiseksi.

Merkkikartan vertailu

Tässä lähestymistavassa luomme ensin merkkikartan createCharMap-funktiomme avulla.

Mikä on merkkikartta?

Kuten tässä yhteydessä käytetään , merkkikarttaobjekti on objekti, joka kuvaa merkkijonon jokaista merkkiä sen esiintymiskertojen määrään merkkijonossa.

Merkkikartan luominenAlhaalla olevassa createCharMap-funktiossamme käytämme for…of-silmukkaa käydessämme läpi saadun merkkijonon jokaisen merkin.

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

Kunkin merkin kohdalla tarkistamme, onko merkki jo olemassa ominaisuutena merkkikartassa charMap käyttäen .hasOwnProperty()-metodia. Jos on, kasvatamme sen arvoa ja jos ei ole, lisäämme merkin ominaisuudeksi ja asetamme sen arvoksi 1.

Loppujen lopuksi palautamme charMap, joka on merkkikarttaobjekti.

Merkkikarttojen vertailuNyt kun meillä on keino merkkikarttojen tuottamiseen, seuraava askel on vertailla molempien merkkijonojen merkkikarttoja, kuten alla olevasta täydellisestä ratkaisusta käy ilmi:

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 }}

Huomaa, että tarkistamme aluksi, ovatko molempien merkkijonojen pituudet samat. Jos ne eivät ole, palautamme false, koska tämä on osoitus siitä, että ne eivät voi koskaan olla anagrammeja. Jos ne kuitenkin ovat, menemme eteenpäin ja luomme niiden merkkikartat, jotka on tallennettu muuttujiin stringAMap ja stringBMap.

Seuraavaksi käytämme for…in-silmukkaa vertaillaksemme jokaista merkkiä ja arvoa stringAMap:ssä merkkiä vastaavaan arvoon stringBMap:ssä. Jos jokin arvo ei täsmää, palautamme false osoituksena siitä, että merkkijonot eivät ole anagrammeja. Jos kaikki arvot kuitenkin täsmäävät, testi on läpäisty ja palautamme true merkkinä siitä, että testatut merkkijonot ovat todellakin anagrammeja.

Tehtiin se. Toteutus on tosiaan pidempi, mutta se on ehdottomasti selittävämpi.

Ajetaanko nyt testit?

Oikeellisuuden testaaminen Jestillä

Kunkin yllä olevan ratkaisun testaamiseksi suorita terminaalista seuraava komento:

npm run test isAnagram

• Suoraa vertailua

• Hahmokarttojen vertailua

Näyttäisi siltä, että pärjäämme aina hienosti! Läpäisimme kaikki testit.

Suorituskyvyn testaaminen JSPerfillä

Tässä suoritamme suorituskykytestin selvittääksemme, kumpi ratkaisu on nopeampi. Alla on kuvakaappaus tuloksesta:

Tuloksesta havaitsemme, että:

Nopeampi toteutus on Character Map Comparison -lähestymistapa ja Direct Comparison -menetelmä, vaikka ytimekäs on noin 52 % hitaampi.

**Yllättävää, eikö olekin? Mittarit eivät kuitenkaan koskaan valehtele!**

Käytännön soveltaminen

Yllä esiteltyjä algoritmeja voidaan soveltaa eri tavoin. Näitä ovat mm:

• Salaus
• Salasanojen generointi
• Luotettava aikaleimaus
• Haastattelujen koodaaminen
• Mnemoniikkojen generointi
• Sanapelit
  

  Johtopäätökset

Harkittaessa edellä tutkittuja tekniikoita ja käsitteitä, olemme oppineet arvokkaita tapoja manipuloida merkkijonoja sen määrittämiseksi, ovatko ne anagrammeja. Tutustuimme myös eri aloihin, joilla tätä tietoa voidaan suoraan hyödyntää.

Suorituskykytestejämme suoritettuamme voimme nyt päätellä, että optimaalisin lähestymistapa tämän ongelman ratkaisemiseen on Character Map Comparison -menetelmä.

Lisälukemista

Jos haluat oppia lisää edellä korostetuista käsitteistä ja tekniikoista, voit käyttää seuraavia linkkejä:

• Regulaariset lausekkeet
• .replace()
• .split()
• .sort()
• .join()
• .hasOwnProperty()
• For…of vs for…in silmukka

Näemme seuraavissa artikkeleissa, joissa keskitytään array-käsittelyalgoritmeihin!✌🏿

Tykkäsitkö tästä artikkelista? Seuraa @worldclassdev Twitterissä