Anagramme

von

Hooray! Dieser Artikel markiert die letzte Herausforderung zur Manipulation von Zeichenketten in diesem Abschnitt des Kurses. Wir haben einen langen Weg hinter uns!

In dieser Aufgabe betrachten wir zwei Möglichkeiten, Anagramme in JavaScript zu erkennen.

Was ist ein Anagramm?

Ein Wort ist ein Anagramm eines anderen, wenn es durch Umstellen der Buchstaben des anderen Wortes gebildet werden kann, wobei jeder Buchstabe nur einmal verwendet wird. Z.B. ist listen ein Anagramm von silent.

Lassen Sie uns loslegen, ja?

Sie sollten Ihre Entwicklungsumgebung für diesen Kurs bereits eingerichtet haben. Aktualisieren Sie Ihr geklontes Repository, indem Sie den Befehl git pull ausführen. Navigieren Sie innerhalb des Ordners Beginner zum Ordner isAnagram. Unsere Arbeit für diese Herausforderung wird hier stattfinden. Vergewissern Sie sich, dass Sie der Datei index-START.js folgen.

Die Herausforderung

Schreiben Sie einen Algorithmus, der prüft, ob zwei Zeichenketten Anagramme voneinander sind. Gib true zurück, wenn sie den Test bestehen, und false, wenn sie es nicht tun. Z.B.

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

Algorithmisches Denken

Bei der Lösung dieser Aufgabe schreiben wir eine Funktion, die zwei Parameter akzeptiert, d.h. die beiden zu vergleichenden Zeichenketten.

BeginnerTailwind.com Learn Tailwind CSS from Scratch

In der Funktion vergleichen wir beide Wörter, um zu sehen, ob sie die gleichen Zeichen enthalten, die gleich oft verwendet werden. Um Fehler zu vermeiden, bereinigen wir die Zeichenkette und entfernen unerwünschte Zeichen und Leerzeichen, da es sich nicht um Buchstaben des Alphabets handelt.

Außerdem konvertieren wir alle Zeichen in eine gemeinsame Groß- und Kleinschreibung, bevor wir Vergleiche durchführen, um Fehler aufgrund unterschiedlicher Großschreibung zu vermeiden. Die Überprüfung, ob beide Wörter gleich lang sind, ist ebenfalls sehr wichtig, da dies ein primärer Faktor für einen gültigen Vergleich ist.

Lassen Sie uns dies tun.

Code-Implementierung

Wir werden nun zwei Möglichkeiten in Betracht ziehen, um unsere Lösung gemäß unserer obigen algorithmischen Logik zu implementieren. Diese sind:

  • Direkter Vergleich
  • Zeichenabbildungsvergleich

Direkter Vergleich

Bei diesem Ansatz definieren wir eine Funktion, die zwei Parameter akzeptiert, d.h. die beiden zu vergleichenden Zeichenfolgen. Anschließend bereinigen wir beide Zeichenketten, um sicherzustellen, dass wir nur Buchstaben und Groß- und Kleinschreibung vergleichen.

Bereinigen der ZeichenketteUm die Zeichenkette zu bereinigen, erstellen wir eine Funktion sanitizeString. Diese Funktion akzeptiert die zu bereinigende Zeichenkette als Parameter und verwendet die Methoden .toLowerCase(), .replace(), .split(), .sort() und .join(), um die Zeichenkette wie folgt zu bearbeiten:

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

Schauen wir uns die Dinge etwas genauer an:

  • Zunächst konvertieren wir die gesamte Zeichenkette mit der Methode .toLowerCase() in Kleinschreibung.
  • Als Nächstes verwenden wir die Methode .replace(), um die Zeichenfolge anhand des angegebenen Musters für reguläre Ausdrücke zu durchsuchen und jedes nicht alphabetische Zeichen durch eine leere Zeichenfolge zu ersetzen. So bleiben nur Buchstaben übrig. Keine Leerzeichen, keine Symbole!
  • Als Nächstes rufen wir .split() auf, um die Zeichenkette in ein Array von Zeichen aufzuteilen.
  • Mit der Methode .sort() sortieren wir die Buchstaben (Elemente) innerhalb des Arrays in alphabetischer Reihenfolge.
  • Und schließlich fügen wir das nun alphabetisch geordnete Array von Buchstaben wieder zusammen, um erneut eine Zeichenkette zu bilden.

Diese Zeichenkette geben wir als bereinigte Zeichenkette zurück.

Glatt!** Richtig?**

Vergleich der bereinigten ZeichenkettenDas Bereinigen der Zeichenkette wie oben beschrieben ist vielleicht der schwierigste Teil dieser Lösung. Als Nächstes bereinigen wir einfach die empfangenen Zeichenfolgen mit der Funktion sanitizeString und vergleichen die Ergebnisse. Wenn beide Zeichenfolgen übereinstimmen, geben wir true zurück, was bedeutet, dass sie als Anagramme durchgehen. Wenn sie nicht übereinstimmen, geben wir false zurück, was bedeutet, dass sie nicht übereinstimmen.

Siehe die vollständige Lösung unten:

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

Einer weniger!** Jetzt wird es noch seltsamer! 😈**

Wie Sie sehen werden, gehen wir bei der Lösung des Problems schrittweise vor.

Vergleich der Zeichenkarten

Bei diesem Ansatz erzeugen wir zunächst eine Zeichenkarte mit unserer Funktion createCharMap.

Was ist eine Zeichentabelle?

In diesem Zusammenhang ist ein Zeichentabellenobjekt ein Objekt, das jedes Zeichen in einer Zeichenkette auf die Anzahl seiner Vorkommen in der Zeichenkette abbildet.

Erstellen der ZeichentabelleIn unserer createCharMap Funktion unten verwenden wir eine for…of-Schleife, um jedes Zeichen der empfangenen Zeichenkette zu durchlaufen.

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

Für jedes Zeichen prüfen wir, ob es bereits als Eigenschaft in der Zeichentabelle charMap vorhanden ist, indem wir die .hasOwnProperty() Methode verwenden. Wenn ja, erhöhen wir seinen Wert, wenn nicht, fügen wir das Zeichen als Eigenschaft hinzu und setzen seinen Wert auf 1.

Am Ende geben wir charMap zurück, das Objekt der Zeichentabelle.

Vergleich der ZeichentabellenNun, da wir eine Möglichkeit haben, die Zeichentabellen zu erzeugen, besteht der nächste Schritt darin, die Zeichentabellen für beide Zeichenketten zu vergleichen, wie in der vollständigen Lösung unten gezeigt wird:

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

Beachten Sie, dass wir zuerst prüfen, ob die Länge der beiden Zeichenketten gleich ist. Ist dies nicht der Fall, geben wir false zurück, da dies ein Indikator dafür ist, dass sie niemals Anagramme sein können. Wenn sie jedoch gleich sind, gehen wir weiter und erzeugen ihre Zeichenkarten, die als Variablen stringAMap und stringBMap gespeichert sind.

Als nächstes verwenden wir die for…in-Schleife, um jedes Zeichen und jeden Wert in stringAMap mit dem entsprechenden Wert in stringBMap zu vergleichen. Wenn ein Wert nicht übereinstimmt, wird false zurückgegeben, um anzuzeigen, dass die Zeichenfolgen keine Anagramme sind. Wenn jedoch alle Werte übereinstimmen, ist der Test bestanden und wir geben true als Hinweis darauf zurück, dass die getesteten Zeichenfolgen tatsächlich Anagramme sind.

Wir haben es geschafft. Es ist zwar eine längere Implementierung, aber auf jeden Fall eine erklärendere.

Lassen Sie uns jetzt unsere Tests durchführen, ja?

Testen der Korrektheit mit Jest

Um jede der obigen Lösungen zu testen, führen Sie den folgenden Befehl in Ihrem Terminal aus:

npm run test isAnagram

  • Direkter Vergleich

  • Vergleich der Zeichenkarten

Es scheint, dass wir immer gut abschneiden! Wir haben alle Tests bestanden.

Leistungstest mit JSPerf

Hier führen wir einen Leistungstest durch, um festzustellen, welche Lösung schneller ist. Nachfolgend finden Sie einen Screenshot des Ergebnisses:

Aus dem Ergebnis geht hervor, dass:

Die schnellere Implementierung ist der Character Map Comparison-Ansatz und die Direct Comparison-Methode ist zwar prägnant, aber etwa 52 % langsamer.

**Überraschend, nicht wahr? Die Metriken lügen aber nie!**

Praktische Anwendung

Die oben untersuchten Algorithmen können auf verschiedene Weise angewendet werden. Dazu gehören:

  • Verschlüsselung
  • Erzeugung von Passwörtern
  • Vertrauenswürdige Zeitstempel
  • Codierung von Interviews
  • Erzeugung von Mnemotechniken
  • Wortspiele

    Schlussfolgerung

Bei der Betrachtung der oben untersuchten Techniken und Konzepte haben wir wertvolle Möglichkeiten zur Manipulation von Algorithmen gelernt, haben wir gelernt, wie man Zeichenketten manipulieren kann, um festzustellen, ob sie Anagramme sind. Wir haben auch verschiedene Bereiche erforscht, in denen dieses Wissen direkt genutzt werden kann.

Nachdem wir unsere Leistungstests durchgeführt haben, können wir nun feststellen, dass der optimale Ansatz zur Lösung dieses Problems die Methode des Zeichenkartenvergleichs ist.

Weiterführende Literatur

Um mehr über die oben hervorgehobenen Konzepte und Techniken zu erfahren, können Sie die folgenden Links verwenden:

  • Regelmäßige Ausdrücke
  • .replace()
  • .split()
  • .sort()
  • .join()
  • .hasOwnProperty()
  • For…of vs for…in loop

See you in the next set of articles focused on array manipulation algorithms!✌🏿

Like this article? Folgen Sie @worldclassdev auf Twitter

Schreibe einen Kommentar