Hogyan lehet megoldani a Sherlock és Anagrams kódolási kihívást a JavaScript-ben

Ez a bejegyzés végigvezeti Önt a „Sherlock és Anagrams” nevű kódolási kihívás megoldásán. Megnézheti a HackerRank-ban.

Sok időt töltöttem azzal, hogy megpróbáltam megoldani, JavaScript-szel. Amikor megpróbáltam google-ben keresni, nem találtam egy tisztességes JS megoldást. Csak egyet találtam, és nem működött megfelelően. Valamennyi magyarázat teljesen kizárt. Ezért úgy döntöttem, hogy írok róla egy cikket, és megpróbálok útközben néhány szép és könnyen emészthető magyarázatot feltenni. Olvass tovább!

VIGYÁZAT: Az alábbi megoldást rövid magyarázatokkal ismertetem az egyes lépésekkel kapcsolatban. Ha ki akarja próbálni magát, álljon meg itt, és keresse fel a HackerRank webhelyét.

Probléma

Két húr egymás anagrammája, ha az egyik húr betűit átrendezhetjük, hogy a másik húr legyen. Adva egy karakterláncot, keresse meg a karakterlánc azon alszámainak számát, amelyek egymás anagrammái.

Például s = anya , az összes anagrammatikus pár listája [ m, m ], [ mo, om ] a [[0], [2]], [[0, 1], [1, 2]] pozícióban .

Korlátok

A bemeneti karakterlánc hossza: 2 ≤ | s | ≤ 100

Az s karakterlánc csak kisbetűket tartalmaz az ascii [az] tartományból.

Elemzés

Először is először - jobban meg kell értenünk az egész problémát. Mi az anagramma? Mi az anagrammatikus pár? Látok egyet? Továbbá, mit is jelent pontosan az alsávok ?

Más szavakkal, tiszta megoldásról kell rendelkeznünk arról, hogy mit próbálunk megoldani, mielőtt megoldanánk.

A probléma leírásából levonhatunk mindent, amire szükségünk van. Sétálj tovább! ?

Úgy gondolom, hogy ez egy jó pillanat, hogy megemlítsem, hogy a kérdéses kihívás a HackerRank weboldal „Szótárak és hasmapsok” részében található. Valószínűleg azt gondolja, hogy az ilyen típusú adatstruktúrát kell használni a megoldás során. ?

Anagrams

Mivel anagrammákat fogunk keresni, kezdjük velük. Amint azt a fentiekben leírtuk, az egyik szó anagramma egy másik, azonos hosszúságú szó, amelyet az előbbi szó ugyanazon karaktereivel hoztak létre.

Tehát meg kell keresnünk a szavakat, és össze kell hasonlítanunk őket más szavakkal, hogy lássuk, vajon anagrammatikus párok-e. Ha megtaláljuk, csak megszámoljuk őket.

Anagrammatikus párok

Mivel láttuk, hogy mi az anagramma, viszonylag könnyen meg kell állapítani, hogy az anagrammatikus pár csak két húr, amely anagrammák. Ilyen például a „mo” és az „om”, vagy a „hallgat” és a „néma”. Meg kell számolnunk, hogy hány ilyen pár található egy adott karakterláncban. Ehhez ezt az eredeti karakterláncot fel kell osztanunk részstringekre.

Substrings

Az alsorok, amint arra a név következtet, egy karaktersorozat részei. Ezek a részek csak betűk vagy betűk lehetnek, például amiket a fenti példában láthattunk - „ m ” vagy „ mo. ”Megoldásunkban az eredeti karakterláncot felosztjuk ilyen alszövegekre, majd átmegyünk rajtuk és elvégezzük az összehasonlítást, amely megmondja, hogy vannak-e közöttük anagrammatikus párok.

Megoldás

Most, hogy elvégeztük elemzésünket, itt a showtime! ?

Összefoglaljuk:

  1. Meg kell találnunk az adott karaktersorozat összes alszövegét - hozzunk létre egy módszert erre.
  2. Képesnek kell lennünk ellenőrizni, hogy két húr anagrammás-e - hozzon létre egy módszert erre.
  3. Számolnunk kell az összes anagrammatikus párral az adott karakterláncban - hozzunk létre egy módszert erre.
  4. Kombináljon mindent felülről, és köpje le az eredményt - hozzon létre egy módszert erre.

Szerezzen be minden alszöveget

Ez lesz a segítő módszerünk az adott karakterlánc összes alszövegének megtalálásához:

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 }

Amint láthatja, O (n²) idő komplexitással rendelkezik. Esetünkben elvégzi a munkát, mert korlátozott a bemeneti karakterlánc hossza (legfeljebb 100 karakter).

Ellenőrizze az anagrammákat

Ez lesz a segítő módszerünk annak ellenőrzésére, hogy két húr anagrammatikus pár-e:

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 }

Ne feledje, hogy feltételeztük, hogy valószínűleg olyan adatstruktúrákat kell használnunk, mint a hashmaps vagy a szótárak (tekintettel arra a szakaszra, ahol ez a kihívás megtalálható a HackerRank-on).

Egy egyszerű JavaScript objektumot használunk a hashmap szerepének eljátszásához. Két iterációt végzünk - húronként egyet. Amikor iterálunk az elsőn, hozzáadjuk a karaktereit kulcsokként a hashmap-hoz, és megszámoljuk azok megjelenését, amelyeket értékeikként tárolunk. Ezután ismét elvégezzük a második karakterláncot. Ellenőrizze, hogy a karakterei vannak-e tárolva a hashmap-ban. Ha igen - csökkentse értéküket. Ha hiányzik a karakter, ami azt jelenti, hogy a két karakterlánc nem anagrammatikus pár, akkor egyszerűen hamis értéket adunk vissza. Ha mindkét hurok befejeződik, akkor igazra térünk vissza, jelezve, hogy az elemzett húrok anagrammatikus párok.

Végezze el a számlálást

Ez az a módszer, ahol a segítő segítségével ellenőrizzük, hogy egy pár anagrammatikus-e, és megszámoljuk. Ezt a JavaScript tömbök és az általuk biztosított módszerek segítségével tesszük. Egy olyan tömböt ismételünk, amely az eredeti karakterlánc összes alszövegét tartalmazza. Ezután megkapjuk a megfelelő elemet, és eltávolítjuk a tömbből. És akkor csinálunk egy másik hurkot ezen a tömbön keresztül, és visszatérünk 1-be, ha azt találjuk, hogy az aktuális elemnek van egy anagramma. Ha nem található semmi, akkor 0-t adunk vissza.

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 }

És a végén

Az egyetlen dolog, amit most meg kell tennie, az összes fenti kombinálása és a kívánt eredmény kiköpése. Így néz ki a végső módszer:

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 }

Lehet, hogy észrevette, itt keresek először duplikátumokat, hogy megtudjam, folytatnám-e tovább. Mintha nincsenek duplikált betűk, akkor nem lehet anagrammal rendelkezni.

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.