Anagrammer

Af

Hej! Denne artikel markerer den sidste udfordring med strengmanipulation i dette afsnit af dette kursus. Vi er kommet langt!

I denne udfordring overvejer vi to måder at opdage anagrammer i JavaScript på.

Hvad er et anagram?

Et ord siges at være et anagram af et andet ord, når det kan dannes ved at omarrangere bogstaverne i det andet ord ved at bruge hvert bogstav kun én gang. F.eks. er listen et anagram af silent.

Lad os komme i gang, ikke sandt?

Du bør allerede have dit udviklingsmiljø oprettet til dette kursus. Opdater dit klonede repository ved at køre kommandoen git pull. Inde i mappen Beginner skal du navigere til mappen isAnagram. Vores arbejde til denne udfordring vil blive udført herinde. Sørg for at følge med i filenindex-START.js.

Udfordringen

Givet to strenge skal du skrive en algoritme til at kontrollere, om de er anagrammer af hinanden. Returner sandt, hvis de består testen, og falsk, hvis de ikke gør. E.g

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

Algoritmisk tænkning

I løsningen af denne udfordring skriver vi en funktion, der accepterer to parametre, dvs. de to strenge, der skal sammenlignes.

BeginnerTailwind.com Lær Tailwind CSS fra bunden

I funktionen sammenligner vi begge ord for at se, om de indeholder de samme tegn, der bruges det samme antal gange. For at undgå fejl sanitiserer vi strengen og slipper dermed af med uønskede tegn og mellemrum, da disse ikke er bogstaver i alfabetet.

Vi konverterer også alle tegn til en fælles bogstavhøjde, inden vi foretager sammenligninger for at undgå fejl som følge af varierende versaler. Det er også meget vigtigt at kontrollere, at begge ord har samme længde, da dette er en primær faktor for en gyldig sammenligning.

Lad os gøre dette.

Kodeimplementering

Vi vil nu overveje to måder at implementere vores løsning på efter vores algoritmiske logik ovenfor. De er:

  • Direkte sammenligning
  • Karakterkort sammenligning

Direkte sammenligning

I denne fremgangsmåde definerer vi en funktion, der accepterer to parametre, dvs. de to strenge, der skal sammenlignes. Derefter går vi i gang med at rydde op i begge strenge for at sikre, at vi kun sammenligner bogstaver og i et almindeligt tilfælde.

Rengøring af strengenFor at rydde op i strengen opretter vi en funktion sanitizeString. Denne funktion accepterer den streng, der skal renses, som parameter og bruger metoderne .toLowerCase(), .replace(), .split(), .sort() og .join() til at manipulere strengen som vist nedenfor:

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

Lader os bryde tingene lidt ned:

  • Først konverterer vi hele strengen til små bogstaver ved hjælp af metoden .toLowerCase().
  • Dernæst bruger vi metoden .replace() til at søge i strengen ved hjælp af det angivne regulære udtryksmønster og erstatter alle tegn, der ikke er alfabetiske, med en tom streng. Dette efterlader os kun med bogstaver. Ingen mellemrum, ingen symboler!
  • Næst kalder vi .split() for at opdele strengen i et array af tegn.
  • Med metoden .sort() sorterer vi bogstaverne (elementerne) i arrayet i alfabetisk rækkefølge.
  • Og til sidst samler vi det nu alfabetisk ordnede array af bogstaver igen for at danne en streng igen.

Denne streng returnerer vi som den sanitiserede streng.

Smooth!** Ikke sandt?**

Sammenligning af de sanitiserede strengeDen sanitiserede streng, som vi har gjort ovenfor, er måske den vanskeligste del af denne løsning. Dernæst renser vi simpelthen de modtagne strenge ved hjælp af sanitizeString-funktionen og sammenligner resultaterne. Hvis begge strenge stemmer overens, returnerer vi true, hvilket betyder, at de passerer som anagrammer. Hvis de ikke passer sammen, returnerer vi false, hvilket betyder, at de ikke er det.

Se den komplette løsning nedenfor:

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

En ned!** Lad os blive mere underlige! 😈**

Som du vil se, følger den fremgangsmåde, vi nu vil overveje, en mere trinvis fremgangsmåde til løsning af problemet.

Sammenligning af tegnkort

I denne fremgangsmåde genererer vi først et tegnkort ved hjælp af vores createCharMap-funktion.

Hvad er et tegnkort?

Som brugt i denne sammenhæng er et tegnkortobjekt et objekt, der kortlægger hvert tegn i en streng til det antal gange, det forekommer i strengen.

Skabelse af tegnkortetI vores createCharMap funktion nedenfor bruger vi en for…of-sløjfe til at iterere gennem hvert tegn i den modtagne streng.

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

For hvert tegn kontrollerer vi, om tegnet allerede findes som en egenskab i tegnkortet charMap ved hjælp af .hasOwnProperty()-metoden. Hvis det gør, øger vi dens værdi, og hvis det ikke gør, tilføjer vi tegnet som en egenskab og sætter dens værdi til 1.

I sidste ende returnerer vi charMap, som er karakterkortobjektet.

Sammenligning af karakterkortNu hvor vi har en måde at generere karakterkortene på, bliver det næste skridt at sammenligne karakterkortene for begge strenge som vist i den komplette løsning nedenfor:

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

Bemærk, at vi først kontrollerer, om længden af de to strenge er ens. Hvis de ikke er det, returnerer vi false, da dette er en indikator for, at de aldrig kan være anagrammer. Hvis de derimod er det, går vi videre og genererer deres tegnkort, der er gemt som variabler stringAMap og stringBMap.

Næst bruger vi for…in-løjpen til at sammenligne hvert tegn og værdi i stringAMap med tegnets tilsvarende værdi i stringBMap. Hvis der er værdier, der ikke stemmer overens, returnerer vi false som en indikation af, at strengene ikke er anagrammer. Hvis alle værdier stemmer overens, er testen imidlertid bestået, og vi returnerer true som en indikation af, at de testede strenge faktisk er anagrammer.

Vi klarede det. Det er ganske vist en længere implementering, men den er bestemt mere forklarende.

Lad os nu køre vores test, ikke?

Test af korrekthed med Jest

For at teste hver løsning ovenfor skal du køre følgende kommando fra din terminal:

  • Direkte sammenligning

  • Karakterkort-sammenligning

Det ser ud til, at vi altid klarer os godt! Vi bestod alle testene.

Test af ydeevne med JSPerf

Her kører vi en ydeevnetest for at afgøre, hvilken løsning der er hurtigere. Find et skærmbillede af resultatet nedenfor:

Fra resultatet kan vi konstatere, at:

Den hurtigere implementering er Character Map Comparison-tilgangen og Direct Comparison-metoden, selvom Concise er ca. 52 % langsommere.

**Overraskende, ikke sandt? Men målingerne lyver aldrig!**

Praktisk anvendelse

De algoritmer, der er undersøgt ovenfor, kan anvendes på forskellige måder. Disse omfatter:

  • Kryptering
  • Password Generation
  • Trusted Time-stamping
  • Kodning af interviews
  • Generering af Mnemonics
  • Vordspil

    Konklusion

Mens man overvejer de teknikker og koncepter, der er udforsket ovenfor, har vi lært værdifulde måder at manipulere strenge på for at afgøre, om de er anagrammer. Vi har også udforsket forskellige områder, hvor denne viden kan udnyttes direkte.

Efter at have udført vores præstationstest kan vi nu konkludere, at den mest optimale metode til løsning af dette problem er Character Map Comparison-metoden.

Yderligere læsning

For at lære mere om de koncepter og teknikker, der er fremhævet ovenfor, kan du bruge følgende links:

  • Regulære udtryk
  • .replace()
  • .split()
  • .sort()
  • .join()
  • .hasOwnProperty()
  • For…of vs. for…in loop

Vi ses i de næste artikler med fokus på algoritmer til array-manipulation!✌🏿

Synes du om denne artikel? Følg @worldclassdev på Twitter

Skriv en kommentar