So lösen Sie die Sherlock- und Anagrams-Codierungsherausforderung in JavaScript

Dieser Beitrag führt Sie durch meine Lösung für eine Codierungsherausforderung namens "Sherlock and Anagrams". Sie können es in HackerRank ansehen.

Ich habe viel Zeit damit verbracht, es mit JavaScript zu lösen. Als ich versuchte, es zu googeln, konnte ich keine anständige JS-Lösung finden. Ich habe nur einen gefunden und er hat nicht richtig funktioniert. Auch Erklärungen kamen überhaupt nicht in Frage. Aus diesem Grund habe ich beschlossen, einen Artikel darüber zu schreiben und einige nette und leicht verdauliche Erklärungen auf den Weg zu bringen. Lesen Sie jetzt weiter!

⚠️VORSICHT: Ich werde meine Lösung unten mit kurzen Erklärungen zu jedem der Schritte ausrollen . Wenn Sie es selbst versuchen möchten, hören Sie bitte hier auf und besuchen Sie die Website von HackerRank.

Problem

Zwei Zeichenfolgen sind Anagramme voneinander, wenn die Buchstaben einer Zeichenfolge neu angeordnet werden können, um die andere Zeichenfolge zu bilden. Bestimmen Sie anhand einer Zeichenfolge die Anzahl der Teilzeichenfolgenpaare der Zeichenfolge, die Anagramme voneinander sind.

Zum Beispiel ist s = Mutter , die Liste aller anagrammatischen Paare ist [ m, m ], [ mo, om ] an den Positionen [[0], [2]], [[0, 1], [1, 2]] .

Einschränkungen

Länge der Eingabezeichenfolge: 2 ≤ | s | ≤ 100

String s enthält nur Kleinbuchstaben aus dem Bereich ascii [az].

Analyse

Das erste zuerst - wir müssen das ganze Problem besser verstehen. Was ist ein Anagramm? Was ist ein anagrammatisches Paar? Kann ich einen sehen? Was genau bedeutet es auch Teilzeichenfolgen ?

Mit anderen Worten, wir müssen ein klares Bild davon haben, was wir zu lösen versuchen, bevor wir es lösen.

Aus der Beschreibung des Problems können wir alles abziehen, was wir brauchen. Geh weiter! ?

Ich denke, dies ist ein guter Moment, um zu erwähnen, dass sich die fragliche Herausforderung im Abschnitt „Wörterbücher und Hashmaps“ auf der HackerRank-Website befindet. Sie werden wahrscheinlich denken, dass Sie diese Art von Datenstruktur verwenden sollten, wenn Sie sie lösen. ?

Anagramme

Da wir nach Anagrammen suchen werden, beginnen wir mit ihnen. Wie oben beschrieben, ist ein Anagramm eines Wortes ein anderes Wort, das dieselbe Länge hat und mit denselben Zeichen aus dem vorherigen Wort erstellt wird.

Wir müssen also nach Wörtern suchen und sie mit anderen Wörtern vergleichen, um festzustellen, ob es sich um anagrammatische Paare handelt. Einmal gefunden, werden wir sie nur zählen.

Anagrammatische Paare

Da wir gesehen haben, was ein Anagramm ist, sollte es relativ einfach sein zu schließen, dass ein anagrammatisches Paar nur zwei Zeichenfolgen sind, die Anagramme sind. Wie "mo" und "om" oder "hören" und "schweigen". Wir müssen zählen, wie viele Paare wie dieses in einer bestimmten Zeichenfolge gefunden werden können. Dazu müssen wir diesen ursprünglichen String in Teilzeichenfolgen aufteilen.

Teilzeichenfolgen

Teilzeichenfolgen sind, wie der Name schon sagt, Teile einer Zeichenfolge. Diese Teile können nur ein Buchstabe oder ein Buchstabenpaar sein, wie wir es im obigen Beispiel gesehen haben - " m " oder " mo " . „In unserer Lösung werden wir die ursprüngliche Zeichenfolge in solche Teilzeichenfolgen aufteilen und dann diese durchgehen und den Vergleich durchführen, um festzustellen, ob wir anagrammatische Paare unter ihnen haben.

Lösung

Nachdem wir unsere Analyse durchgeführt haben, ist Showtime! ?

Fassen wir zusammen:

  1. Wir müssen alle Teilzeichenfolgen der angegebenen Zeichenfolge finden - erstellen Sie eine Methode dafür.
  2. Wir müssen in der Lage sein zu überprüfen, ob zwei Zeichenfolgen Anagramme sind - erstellen Sie eine Methode dafür.
  3. Wir müssen alle anagrammatischen Paare in der angegebenen Zeichenfolge zählen - erstellen Sie eine Methode dafür.
  4. Kombiniere alles von oben und spucke das Ergebnis aus - erstelle eine Methode dafür.

Holen Sie sich alle Teilzeichenfolgen

Dies ist unsere Hilfsmethode zum Auffinden aller Teilzeichenfolgen einer bestimmten Zeichenfolge:

function getAllSubstrings(str) { let i, j, result = []; for (i = 0; i < str.length; i++) { for (j = i + 1; j < str.length + 1; j++) { result.push(str.slice(i, j)) } } return result }

Wie Sie sehen können, hat es eine zeitliche Komplexität von O (n²). In unserem Fall ist dies der Fall, da die Länge der Eingabezeichenfolge begrenzt ist (bis zu 100 Zeichen).

Suchen Sie nach Anagrammen

Dies ist unsere Hilfsmethode, um zu überprüfen, ob zwei Zeichenfolgen anagrammatische Paare sind:

function isAnagram(str1, str2) { const hist = {} for (let i = 0; i < str1.length; i++) { const char = str1[i] if (hist[char]) { hist[char]++ } else { hist[char] = 1 } } for (let j = 0; j < str2.length; j++) { const char = str2[j] if (hist[char]) { hist[char]-- } else { return false } } return true }

Denken Sie daran, dass wir davon ausgegangen sind, dass wir höchstwahrscheinlich Datenstrukturen wie Hashmaps oder Wörterbücher verwenden müssen (angesichts des Abschnitts, in dem sich diese Herausforderung auf HackerRank befindet).

Wir verwenden ein einfaches JavaScript-Objekt, um die Rolle einer Hashmap zu spielen. Wir machen zwei Iterationen - eine pro String. Wenn wir über das erste iterieren, fügen wir seine Zeichen als Schlüssel zur Hashmap hinzu und zählen ihre Erscheinungen, die als ihre Werte gespeichert werden. Dann machen wir eine weitere Iteration über die zweite Zeichenfolge. Überprüfen Sie, ob die Zeichen in unserer Hashmap gespeichert sind. Wenn ja - verringern Sie ihren Wert. Wenn Zeichen fehlen, was bedeutet, dass die beiden Zeichenfolgen kein anagrammatisches Paar sind, geben wir einfach false zurück. Wenn beide Schleifen abgeschlossen sind, geben wir true zurück, was bedeutet, dass die zu analysierenden Zeichenfolgen ein anagrammatisches Paar sind.

Zähle

Dies ist die Methode, bei der wir den Helfer verwenden, um zu überprüfen, ob ein Paar anagrammatisch ist, und es zu zählen. Wir tun dies mit Hilfe von JavaScript-Arrays und den von ihnen bereitgestellten Methoden. Wir iterieren über ein Array, das alle Teilzeichenfolgen der ursprünglichen Zeichenfolge enthält. Dann erhalten wir das richtige Element und entfernen es aus dem Array. Und dann machen wir eine weitere Schleife durch dieses Array und geben 1 zurück, wenn wir feststellen, dass es ein Anagramm des aktuellen Elements gibt. Wenn nichts gefunden wird, geben wir 0 zurück.

function countAnagrams(currentIndex, arr) { const currentElement = arr[currentIndex] const arrRest = arr.slice(currentIndex + 1) let counter = 0 for (let i = 0; i < arrRest.length; i++) { if (currentElement.length === arrRest[i].length && isAnagram(currentElement, arrRest[i])) { counter++ } } return counter }

Und am Ende

Jetzt müssen Sie nur noch alle oben genannten Punkte kombinieren und das gewünschte Ergebnis erzielen. So sieht die endgültige Methode aus:

function sherlockAndAnagrams(s) { const duplicatesCount = s.split('').filter((v, i) => s.indexOf(v) !== i).length if (!duplicatesCount) return 0 let anagramsCount = 0 const arr = getAllSubstrings(s) for (let i = 0; i < arr.length; i++) { anagramsCount += countAnagrams(i, arr) } return anagramsCount }

Vielleicht haben Sie bemerkt, dass ich hier zuerst nach Duplikaten suche, um zu wissen, ob ich weiter machen soll. Als ob es keine doppelten Buchstaben gibt, ist es nicht möglich, ein Anagramm zu haben.

And finally, we get all substrings into an array, iterate over it, count the anagrammatic pairs that are found and return this number.

You can find the full code here.

Conclusion

These kind of exercises are very good for making you think algorithmically. Also they change your way of working in your day to day job. My recommendation would be to do the same I am trying to do — train your brain now and then with one of those. And if you can — share. I know sometimes you don’t have time for such challenges, but when you do — go for it.

My personal feeling after finishing this was total satisfaction, which is completely understandable, considering the time it took me to do it. But in the end, dear reader, I am even happier I can share this experience with you?!

Thanks for reading. Read more of my articles at mihail-gaberov.eu.