Anagram

Hurra! Den här artikeln markerar den sista utmaningen för hantering av strängar i det här avsnittet av kursen. Vi har kommit långt!

I den här utmaningen undersöker vi två sätt att upptäcka anagram i JavaScript.

Vad är ett anagram?

Ett ord sägs vara ett anagram av ett annat när det kan bildas genom att ordna om bokstäverna i det andra ordet genom att använda varje bokstav bara en gång. Exempelvis är listen ett anagram av silent.

Ska vi sätta igång?

Du bör redan ha din utvecklingsmiljö inställd för den här kursen. Uppdatera ditt klonade arkiv genom att köra kommandot git pull. I mappen Beginner navigerar du till mappen isAnagram. Vårt arbete för den här utmaningen kommer att göras här. Se till att följa med i filen index-START.js.

Utmaningen

Givet två strängar, skriv en algoritm för att kontrollera om de är anagram till varandra. Återge sant om de klarar testet och falskt om de inte gör det. E.g

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

Algoritmiskt tänkande

För att lösa den här utmaningen skriver vi en funktion som accepterar två parametrar, dvs. de två strängar som ska jämföras.

BeginnerTailwind.com Lär dig Tailwind CSS från början

Inom funktionen jämför vi de båda orden för att se om de innehåller samma tecken som används lika många gånger. För att undvika fel sanerar vi strängen och blir därmed av med oönskade tecken och mellanslag eftersom dessa inte är bokstäver i alfabetet.

Vi omvandlar också alla tecken till en gemensam bokstavsform innan vi utför jämförelser för att undvika fel på grund av varierande versaler. Att kontrollera att båda orden har samma längd är också mycket viktigt eftersom detta är en primär faktor för en giltig jämförelse.

Vi gör detta.

Kodimplementering

Vi kommer nu att överväga två sätt att implementera vår lösning enligt vår algoritmiska logik ovan. De är:

• Direkt jämförelse
• Karakterkortsjämförelse

Direkt jämförelse

I det här tillvägagångssättet definierar vi en funktion som accepterar två parametrar, dvs. de två strängar som ska jämföras. Därefter rensar vi upp de båda strängarna för att se till att vi endast jämför bokstäver och i ett vanligt fall.

Rensning av strängenFör att rensa upp strängen skapar vi en funktion sanitizeString. Denna funktion tar emot strängen som ska saneras som en parameter och använder metoderna .toLowerCase(), .replace(), .split(), .sort() och .join() för att manipulera strängen enligt nedan:

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

Låt oss bryta ner saker och ting lite:

• Först konverterar vi hela strängen till små bokstäver med hjälp av metoden .toLowerCase().
• Nästan använder vi metoden .replace() för att söka igenom strängen med hjälp av det angivna reguljära uttrycksmönstret och ersätta varje tecken som inte är alfabetiskt med en tom sträng. Detta lämnar oss med endast bokstäver. Inga mellanslag, inga symboler!
• Nästan anropar vi .split() för att dela upp strängen i en array av tecken.
• Med hjälp av metoden .sort() sorterar vi bokstäverna (elementen) i arrayen i alfabetisk ordning.
• Och till sist sammanfogar vi den nu alfabetiskt ordnade arrayen av bokstäver igen för att återigen bilda en sträng.

Denna sträng är vad vi returnerar som den sanerade strängen.

Smooth!** Eller hur?**

Genom att jämföra de sanerade strängarnaSaneringen av strängen som gjorts ovan är kanske den knepigaste delen av denna lösning. Därefter rensar vi helt enkelt upp de strängar som tagits emot med hjälp av funktionen sanitizeString och jämför resultaten. Om båda strängarna stämmer överens returnerar vi true som anger att de passerar som anagram. Om de inte stämmer överens returnerar vi false som anger att de inte är det.

Se den fullständiga lösningen nedan:

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

En klar!** Nu blir det konstigare! 😈**

Som du kommer att se följer det tillvägagångssätt som vi nu ska överväga en mer stegvis procedur för att lösa problemet.

Jämförelse av teckenkartor

I det här tillvägagångssättet genererar vi först en teckenkarta med hjälp av vår createCharMap-funktion.

Vad är en teckenmappning?

Som används i detta sammanhang är ett teckenmappningsobjekt ett objekt som mappar varje tecken i en sträng till det antal gånger det förekommer i strängen.

Skapande av teckenkartanI vår createCharMap funktion nedan använder vi en for…of-slinga för att iterera genom varje tecken i den mottagna strängen.

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

För varje tecken kontrollerar vi om tecknet redan finns som en egenskap i teckenkartan charMap med hjälp av .hasOwnProperty()-metoden. Om det gör det, ökar vi dess värde och om det inte gör det, lägger vi till tecknet som en egenskap och sätter dess värde till 1.

I slutändan returnerar vi charMap som är teckenmappobjektet.

Genom att vi har ett sätt att generera teckenmapparna blir nästa steg att jämföra teckenmapparna för de båda strängarna enligt den kompletta lösningen nedan:

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 att vi först kontrollerar om längden på de båda strängarna är lika. Om de inte är det returnerar vi false eftersom detta är en indikator på att de aldrig kan vara anagram. Om de däremot är det, går vi vidare och genererar deras teckenkartor som lagras som variablerna stringAMap och stringBMap.

Nästan använder vi for…in-slingan för att jämföra varje tecken och värde i stringAMap med tecknets motsvarande värde i stringBMap. Om något värde inte stämmer överens returnerar vi false som en indikation på att strängarna inte är anagram. Men om alla värden stämmer överens är testet godkänt och vi returnerar true som en indikation på att de testade strängarna verkligen är anagram.

Vi klarade det. Ett längre genomförande förvisso, men det är definitivt mer förklarande.

Vi kan väl köra våra tester nu?

Testa korrekthet med Jest

För att testa varje lösning ovan kör du följande kommando från din terminal:

• Direkt jämförelse

• Karaktärsortsjämförelse

Det verkar som om vi alltid gör bra ifrån oss! Vi klarade alla tester.

Test av prestanda med JSPerf

Här kör vi ett prestandatest för att avgöra vilken lösning som är snabbare. Hitta en skärmdump av resultatet nedan:

Från resultatet kan vi konstatera att:

Den snabbare implementeringen är Character Map Comparison-metoden och Direct Comparison-metoden även om concise är cirka 52 % långsammare.

**Overraskande, eller hur? Mätvärdena ljuger aldrig!**

Praktisk tillämpning

De algoritmer som undersökts ovan kan tillämpas på olika sätt. Dessa inkluderar:

• Kryptering
• Passordsgenerering
• Trusted Time-stamping
• Kodning av intervjuer
• Generering av minnesanteckningar
• Vordspel
  

  Slutsats

Men samtidigt som vi funderar över de tekniker och begrepp som undersökts ovan, har vi lärt oss värdefulla sätt att manipulera strängar för att avgöra om de är anagram. Vi har också utforskat olika områden där denna kunskap kan användas direkt.

Efter att ha kört våra prestandatester kan vi nu dra slutsatsen att den mest optimala metoden för att lösa detta problem är Character Map Comparison-metoden.

Ytterligare läsning

För att lära dig mer om de begrepp och tekniker som lyfts fram ovan kan du använda följande länkar:

• Regulära uttryck
• .replace()
• .split()
• .sort()
• .join()
• .hasOwnProperty()
• For…of vs for…in loop

Vi ses i nästa artikelserie som fokuserar på algoritmer för hantering av matriser!✌🏿

Gillar du denna artikel? Följ @worldclassdev på Twitter