Kaip išspręsti „Sherlock“ ir „Anagrams“ kodavimo iššūkį „JavaScript“

Šis įrašas padės jums sužinoti mano kodavimo iššūkio, pavadinto „Šerlokas ir Anagramai“, sprendimą. Galite pažvelgti į tai „HackerRank“.

Aš praleidau daug laiko bandydamas tai išspręsti su „JavaScript“. Kai bandžiau „Google“ jį rasti, negalėjau rasti tinkamo JS sprendimo. Aš radau tik vieną, ir jis neveikė tinkamai. Be to, apie bet kokius paaiškinimus nebuvo nė kalbos. Štai kodėl nusprendžiau parašyti apie tai straipsnį ir pabandyti pateikti keletą gražių ir lengvai virškinamų paaiškinimų. Skaityk dabar!

ATSARGIAI: Žemiau išdėstysiu savo sprendimą su trumpais paaiškinimais apie kiekvieną veiksmą . Jei norite išbandyti patys, užsukite čia ir eikite į „HackerRank“ svetainę.

Problema

Dvi stygos yra viena kitos anagramos, jei vienos eilutės raides galima pertvarkyti, kad susidarytų kita eilutė. Atsižvelgdami į eilutę, suraskite eilutės pakraščių porų, kurios yra viena kitos anagramos, skaičių.

Pavyzdžiui, s = mama , visų anagrammatinių porų sąrašas yra [ m, m ], [ mo, om ] atitinkamai [[0], [2]], [[0, 1], [1, 2]] pozicijose. .

Apribojimai

Įvesties eilutės ilgis: 2 ≤ | s | ≤ 100

Eilutėse s yra tik mažosios raidės nuo ascii [az] diapazono.

Analizė

Pirmiausia pirmiausia turime geriau suprasti visą problemą. Kas yra anagrama? Kas yra anagramatinė pora? Ar galiu pamatyti vieną? Be to, ką tai tiksliai reiškia poskyrius ?

Kitaip tariant, prieš spręsdami turime turėti aiškų vaizdą apie tai, ką bandome išspręsti.

Iš problemos aprašymo galime išskaičiuoti viską, ko mums reikia. Eik toliau! ?

Manau, kad tai tinkamas momentas paminėti, kad nagrinėjamas iššūkis yra „HackerRank“ svetainės skyriuje „Žodynai ir„ Hashmaps “. Tikriausiai pagalvosite, kad spręsdami turėtumėte naudoti tokią duomenų struktūrą. ?

Anagramos

Kadangi ketiname ieškoti anagramų, pradėkime nuo jų. Kaip aprašyta aukščiau, vieno žodžio anagrama yra kitas vienodo ilgio žodis, sukurtas su tais pačiais ankstesnio žodžio simboliais.

Taigi turėsime ieškoti žodžių ir palyginti juos su kitais žodžiais, kad pamatytume, ar tai anagramatinės poros. Suradę juos tiesiog suskaičiuosime.

Anagramminės poros

Kadangi mes matėme, kas yra anagrama, turėtų būti gana lengva padaryti išvadą, kad anagramatinė pora yra tik dvi stygos, kurios yra anagramos. Tokie kaip „mo“ ir „om“, arba „klausyk“ ir „tyli“. Turėsime suskaičiuoti, kiek tokių porų galima rasti tam tikroje eilutėje. Norėdami tai padaryti, turime suskaidyti šią originalią eilutę į eilutes.

Substringai

Substringai, kaip rodo pavadinimas, yra eilutės dalys. Šios dalys gali būti tik raidė arba raidžių pora, pavyzdžiui, tai, ką matėme aukščiau pateiktame pavyzdyje - „ m “ arba „ mo“. „Savo sprendime pradinę eilutę suskaidysime į tokius pakraščius, tada pereisime per juos ir atliksime palyginimą, kuris mums pasakys, ar turime anagramatinių porų.

Sprendimas

Dabar, kai mes atlikome analizę, atėjo laikas! ?

Apibendrinkime:

  1. Turime rasti visus nurodytos eilutės pakraščius - sukurkite tam metodą.
  2. Turime mokėti patikrinti, ar dvi eilutės yra anagramos - sukurkite tam metodą.
  3. Turime suskaičiuoti visas anagramatines poras pateiktoje eilutėje - sukurkite tam metodą.
  4. Sujunkite viską iš viršaus ir išspjaukite rezultatą - sukurkite tam metodą.

Gauti visus pakraščius

Tai bus mūsų pagalbinis metodas ieškant visų nurodytos eilutės pakraščių:

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 }

Kaip matote, jis turi O (n²) laiko sudėtingumą. Mūsų atveju jis atlieka darbą, nes įvesties eilutės ilgis yra ribotas (iki 100 simbolių).

Patikrinkite, ar nėra anagramų

Tai bus mūsų pagalbinis metodas patikrinti, ar dvi eilutės yra anagramatinės poros:

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 }

Atminkite, kad manėme, jog greičiausiai turėtume naudoti duomenų struktūras, tokias kaip hashmaps ar žodynus (atsižvelgiant į skyrių, kuriame šis iššūkis yra „HackerRank“).

Mes naudojame paprastą „JavaScript“ objektą, kad atliktume „hashmap“ vaidmenį. Mes atliekame dvi iteracijas - po vieną eilutėje. Kartodami pirmąjį, pridedame jo simbolius kaip raktus į hashmap ir suskaičiuojame jų pasirodymus, kurie bus saugomi kaip jų vertės. Tada mes darome pakartojimą per antrą eilutę. Patikrinkite, ar jo simboliai yra saugomi mūsų hashmap. Jei taip - sumažinkite jų vertę. Jei trūksta simbolių, o tai reiškia, kad dvi eilutės nėra anagramatinė pora, mes tiesiog pateikiame klaidingą. Jei baigsis abi kilpos, mes grįšime į tiesą, nurodydami, kad analizuojamos stygos yra anagramatinė pora.

Atlikite skaičiavimą

Tai yra metodas, kai mes naudosime pagalbininką patikrindami, ar pora yra anagramatinė, ir suskaičiuosime. Tai darome pasitelkdami „JavaScript“ masyvus ir jų teikiamus metodus. Kartojame masyvą, kuriame yra visi pradinės eilutės pakraščiai. Tada gauname teisingą elementą ir pašaliname jį iš masyvo. Tada mes darome kitą kilpą per tą masyvą ir grąžiname 1, jei nustatome, kad yra dabartinio elemento anagrama. Jei nieko nerandama, grąžiname 0.

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 }

Ir galų gale

Vienintelis dalykas, kurį dabar reikia padaryti, yra sujungti visus aukščiau išdėstytus dalykus ir išspjauti norimą rezultatą. Štai kaip atrodo galutinis metodas:

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 }

Gal pastebėjote, čia pirmiausia tikrinu, ar nėra dublikatų, kad sužinotumėte, ar turėčiau tęsti toliau. Tarsi nebūtų dubliuotų raidžių, tada anagramos turėti neįmanoma.

Galiausiai, mes gauname visus poskirsnius į masyvą, kartojame jį, suskaičiuojame randamas anagrammatines poras ir grąžiname šį skaičių.

Visą kodą rasite čia.

Išvada

Šie pratimai yra labai geri, kad priverstumėte mąstyti algoritmiškai. Be to, jie keičia jūsų kasdienio darbo būdą. Mano rekomendacija būtų daryti tą patį, ką ir aš bandau - treniruokitės savo smegenis kartais su vienu iš tų. O jei gali - dalinkis. Žinau, kad kartais neturite laiko tokiems iššūkiams, bet kai turite - eikite į tai.

Mano asmeninis jausmas baigus tai buvo visiškas pasitenkinimas, kuris yra visiškai suprantamas, atsižvelgiant į tai, kiek laiko užtrukau tai padaryti. Bet galų gale, mielas skaitytojau, esu dar laimingesnė, galėdama pasidalinti šia patirtimi su jumis ?!

Ačiū, kad skaitėte. Skaitykite daugiau mano straipsnių mihail-gaberov.eu.