Anagrammen

Hooray! Dit artikel markeert de laatste string manipulatie uitdaging in dit deel van deze cursus. We hebben een lange weg afgelegd!

In deze uitdaging bekijken we twee manieren om anagrammen in JavaScript te detecteren.

Wat is een anagram?

Een woord wordt een anagram van een ander woord genoemd als het kan worden gevormd door de letters van het andere woord te herschikken, waarbij elke letter slechts één keer wordt gebruikt. Bijvoorbeeld: listen is een anagram van silent.

Laten we aan de slag gaan, zullen we?

Je zou je ontwikkelomgeving al moeten hebben ingesteld voor deze cursus. Update je gekloonde repository door het commando git pull uit te voeren. Navigeer in de Beginner map naar de isAnagram map. Ons werk voor deze uitdaging zal hierin gedaan worden. Zorg ervoor dat je meekijkt in het bestandindex-START.js.

De uitdaging

Geef twee strings, schrijf een algoritme om te controleren of ze anagrammen van elkaar zijn. Geef true terug als ze de test doorstaan en false als dat niet het geval is. Bv

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

Algoritmisch denken

Bij het oplossen van deze uitdaging schrijven we een functie die twee parameters accepteert, namelijk de twee strings die vergeleken moeten worden.

BeginnerTailwind.com Learn Tailwind CSS from Scratch

In de functie vergelijken we beide woorden om te zien of ze dezelfde karakters bevatten die hetzelfde aantal keren zijn gebruikt. Om fouten te voorkomen, zuiveren we de string en verwijderen we ongewenste tekens en spaties omdat dit geen letters van het alfabet zijn.

We zetten ook alle tekens om in een gewone hoofdletter voordat we vergelijkingen uitvoeren om fouten door verschillend hoofdlettergebruik te voorkomen. Controle of beide woorden even lang zijn is ook erg belangrijk, omdat dit een primaire factor is voor een geldige vergelijking.

Laten we dit doen.

Code-implementatie

We zullen nu twee manieren overwegen om onze oplossing te implementeren volgens onze algoritmische logica hierboven. Deze zijn:

• Directe vergelijking
• Character Map Comparison

Directe vergelijking

In deze aanpak definiëren we een functie die twee parameters accepteert, d.w.z. de twee strings die moeten worden vergeleken. Vervolgens schonen we beide strings op om er zeker van te zijn dat we alleen letters vergelijken en in een gangbare vorm.

Om de string op te schonen, maken we een functie sanitizeString. Deze functie accepteert de string die moet worden opgeschoond als parameter en gebruikt de methoden .toLowerCase(), .replace(), .split(), .sort() en .join() om de string te manipuleren, zoals hieronder wordt getoond:

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

Laten we de zaken een beetje uitsplitsen:

• Eerst zetten we de hele string om in kleine letters met behulp van de methode .toLowerCase().
• Daarna gebruiken we de methode .replace() om de tekenreeks te doorzoeken met behulp van het opgegeven reguliere expressiepatroon en vervangen we elk niet-alfabetisch teken door een lege tekenreeks. Dit laat ons alleen letters over. Geen spaties, geen symbolen!
• Daarna roepen we .split() op om de string in een array van tekens te splitsen.
• Met behulp van de methode .sort() sorteren we de letters (elementen) in de array in alfabetische volgorde.
• En tenslotte voegen we de nu alfabetisch geordende array van letters weer samen om weer een string te vormen.

Deze string geven we terug als de opgeschoonde string.

Smooth!** Toch?

De opgeschoonde strings vergelijkenHet opgeschonen van de string, zoals hierboven gedaan, is misschien wel het lastigste deel van deze oplossing. Vervolgens schonen we de ontvangen strings op met de sanitizeString functie en vergelijken de resultaten. Als beide strings overeenkomen, geven we true terug om aan te geven dat ze anagrammen zijn. Komen ze niet overeen, dan geven we false terug, ten teken dat ze dat niet zijn.

Zie de volledige oplossing hieronder:

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

Eén neer!**Laten we nog vreemder worden! 😈**

Zoals u zult zien, volgt de aanpak die we nu zullen overwegen een meer stapsgewijze procedure om het probleem op te lossen.

Karakter Kaart Vergelijking

In deze aanpak genereren we eerst een karakterkaart met behulp van onze createCharMap functie.

Wat is een tekenkaart?

In deze context is een tekenkaartobject een object dat elk teken in een tekenreeks koppelt aan het aantal keren dat het in de tekenreeks voorkomt.

De tekenmap makenIn onze createCharMap-functie hieronder gebruiken we een for…of-lus om elk teken van de ontvangen tekenreeks te doorlopen.

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

Voor elk teken controleren we of het teken al bestaat als een eigenschap in de tekenmap charMap met behulp van de .hasOwnProperty()-methode. Zo ja, dan verhogen we de waarde en zo nee, dan voegen we het karakter toe als eigenschap en stellen de waarde in op 1.

Uiteindelijk geven we charMap terug, dat is het tekenmap-object.

Vergelijken van tekenmappenNu we een manier hebben om de tekenmappen te genereren, bestaat de volgende stap uit het vergelijken van de tekenmappen voor beide strings, zoals in de volledige oplossing hieronder wordt getoond:

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

Merk op dat we eerst controleren of de lengte van beide strings gelijk is. Als dat niet zo is, geven we false terug, omdat dit een indicator is dat ze nooit anagrammen kunnen zijn. Als dat wel het geval is, gaan we verder en genereren we hun tekenkaarten, die worden opgeslagen als variabelen stringAMap en stringBMap.

Daarna gebruiken we de for…in-lus om elk teken en elke waarde in stringAMap te vergelijken met de corresponderende waarde van het teken in stringBMap. Als er waarden zijn die niet overeenkomen, geven we false terug als teken dat de strings geen anagrammen zijn. Als echter alle waarden overeenkomen, is de test geslaagd en geven we true terug als teken dat de geteste strings inderdaad anagrammen zijn.

We hebben het gehaald. Een langere implementatie inderdaad, maar het is zeker een meer verklarende.

Laten we nu onze tests uitvoeren, zullen we?

Correctheid testen met Jest

Om elke bovenstaande oplossing te testen, voert u het volgende commando uit vanaf uw terminal:

npm run test isAnagram

• Directe vergelijking

• Vergelijking van de tekenmap

Het blijkt dat we het altijd goed doen! We zijn voor alle tests geslaagd.

Prestatietests met JSPerf

Hier voeren we een prestatietest uit om te bepalen welke oplossing sneller is. Hieronder vindt u een screenshot van het resultaat:

Uit het resultaat kunnen we opmaken dat:

De snelste implementatie is de Character Map Comparison-methode en de Direct Comparison-methode, hoewel deze beknopt ongeveer 52% langzamer is.

** Verrassend, nietwaar? De metingen liegen echter nooit!**

Praktische toepassing

De hierboven onderzochte algoritmen kunnen op verschillende manieren worden toegepast. Deze omvatten:

• Encryptie
• Paswoordgeneratie
• Trusted Time-stamping
• Coding Interviews
• Generating Mnemonics
• Word games
  

  Conclusie

Tijdens het beschouwen van de technieken en concepten die hierboven zijn verkend, hebben we waardevolle manieren geleerd om strings te manipuleren om te bepalen of ze anagrammen zijn. We hebben ook verschillende gebieden verkend waarin deze kennis direct kan worden gebruikt.

Na het uitvoeren van onze prestatietests kunnen we nu concluderen dat de meest optimale benadering om dit probleem op te lossen de Character Map Comparison-methode is.

Verder lezen

Om meer te weten te komen over de hierboven beschreven concepten en technieken, kunt u de volgende koppelingen gebruiken:

• Reguliere uitdrukkingen
• .replace()
• .split()
• .sort()
• .join()
• .hasOwnProperty()
• Voor…van vs voor…in lus

Tot ziens in de volgende serie artikelen over array manipulatie algoritmes!✌🏿

Vind je dit artikel leuk? Volg @worldclassdev op Twitter