Sådan løses Sherlock og Anagrams kodning udfordring i JavaScript

Dette indlæg vil bringe dig igennem min løsning på en kodningsudfordring kaldet "Sherlock and Anagrams." Du kan se på det i HackerRank.

Jeg brugte meget tid på at prøve at løse det med JavaScript. Da jeg forsøgte at google det, kunne jeg ikke finde en anstændig JS-løsning. Jeg fandt kun en, og den fungerede ikke korrekt. Også eventuelle forklaringer var helt ude af spørgsmålet. Derfor besluttede jeg at skrive en artikel om det og prøve at sætte nogle gode og letfordøjelige forklaringer undervejs. Fortsæt med at læse nu!

CA️FORSIGTIG: Jeg vil udrulle min løsning nedenfor med korte forklaringer om hvert trin. Hvis du selv vil prøve, skal du stoppe her og gå til HackerRanks websted.

Problem

To strenge er anagrammer over hinanden, hvis bogstaverne i den ene streng kan arrangeres for at danne den anden streng. Givet en streng, find antallet af par af strenge af strengen, der er anagrammer over hinanden.

For eksempel er s = mor , listen over alle anagrammatiske par er henholdsvis [ m, m ], [ mo, om ] i positionerne [[0], [2]], [[0, 1], [1, 2]] .

Begrænsninger

Indgangsstrengens længde: 2 ≤ | s | ≤ 100

Streng s indeholder kun små bogstaver fra området ascii [az].

Analyse

Første ting først - vi er nødt til at få en bedre forståelse af hele problemet. Hvad er et anagram? Hvad er et anagrammatisk par? Kan jeg se en? Hvad betyder det præcist underlag ?

Med andre ord skal vi have et klart billede af, hvad vi prøver at løse, inden vi løser det.

Fra beskrivelsen af ​​problemet kan vi trække alt, hvad vi har brug for. Bliv ved med at gå! ?

Jeg synes, det er et godt øjeblik at nævne, at den pågældende udfordring er under afsnittet "Ordbøger og hashmaps" på HackerRank-webstedet. Du vil sandsynligvis synes, at du skal bruge denne form for datastruktur, når du løser den. ?

Anagrammer

Da vi skal kigge efter anagrammer, lad os starte med dem. Som det er beskrevet ovenfor, er et anagram med et ord et andet ord, der har samme længde og er oprettet med de samme tegn fra det tidligere ord.

Så vi bliver nødt til at kigge efter ord og sammenligne dem med andre ord for at se, om de er anagrammatiske par. Når de er fundet, tæller vi dem bare.

Anagrammatiske par

Da vi har set, hvad et anagram er, bør det være relativt let at konkludere, at et anagrammatisk par kun er to strenge, der er anagrammer. Såsom “mo” og “om” eller “lyt” og “tavs”. Vi bliver nødt til at tælle, hvor mange par som dette der findes i en given streng. For at gøre det skal vi opdele denne originale streng til understrenge.

Understrenge

Substrings, som navnet udledes, er dele af en streng. Disse dele kan kun være et bogstav eller et par bogstaver, såsom hvad vi har set i eksemplet ovenfor - “ m ” eller “ mo. ”I vores løsning deler vi den originale streng til sådanne understrenge, og så går vi over dem og foretager sammenligningen, som fortæller os, om vi har anagrammatiske par blandt dem.

Opløsning

Nu hvor vi har foretaget vores analyse, er det showtime! ?

Lad os sammenfatte:

  1. Vi er nødt til at finde alle understrenge af den givne streng - lav en metode til det.
  2. Vi skal være i stand til at kontrollere, om to strenge er anagrammer - lav en metode til det.
  3. Vi skal tælle alle anagrammatiske par i den givne streng - lav en metode til det.
  4. Kombiner alt ovenfra og spyt resultatet - lav en metode til det.

Få alle underlag

Dette vil være vores hjælpemetode til at finde alle understrenge af en given streng:

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 }

Som du kan se, har den O (n²) tidskompleksitet. For vores sag gør det jobbet, fordi vi har begrænset længde på inputstrengen (op til 100 tegn).

Se efter anagrammer

Dette vil være vores hjælpemetode til at kontrollere, om to strenge er anagrammatiske par:

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 }

Husk, at vi antog, at vi sandsynligvis skulle bruge datastrukturer som hashmaps eller ordbøger (givet det afsnit, hvor denne udfordring findes på HackerRank).

Vi bruger et simpelt JavaScript-objekt til at spille rollen som en hashmap. Vi laver to iterationer - en pr. Streng. Når vi gentager den første, tilføjer vi dens tegn som nøgler til hashmap og tæller deres udseende, som vil blive gemt som deres værdier. Så laver vi en anden iteration over den anden streng. Kontroller, om dens tegn er gemt i vores hashmap. Hvis ja - mindsk deres værdi. Hvis der mangler tegn, hvilket betyder, at de to strenge ikke er et anagrammatisk par, returnerer vi simpelthen falsk. Hvis begge sløjfer er færdige, vender vi tilbage sandt, hvilket betyder, at strengene, der analyseres, er et anagrammatisk par.

Gør tællingen

Dette er metoden, hvor vi bruger hjælperen til at kontrollere, om et par er anagrammatisk og tæller det. Vi gør det ved hjælp af JavaScript-arrays og de metoder, de giver. Vi gentages over en matrix, der indeholder alle understrengene i den originale streng. Så får vi det rigtige element og fjerner det fra arrayet. Og så laver vi en anden sløjfe gennem det array og returnerer 1, hvis vi finder ud af, at der er et anagram over det aktuelle element. Hvis der ikke findes noget, returnerer vi 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 }

Og til sidst

Det eneste, der skal gøres nu, er at kombinere alt det ovenstående og spytte det ønskede resultat. Sådan ser den endelige metode ud:

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 }

Måske har du bemærket, her kontrollerer jeg først for duplikater for at vide, om jeg skal fortsætte videre. Som om der ikke er nogen duplikerede bogstaver, er det ikke muligt at have et anagram.

Og til sidst får vi alle understrengninger ind i en matrix, gentages over den, tæller de anagrammatiske par, der findes, og returnerer dette tal.

Du kan finde den fulde kode her.

Konklusion

Denne form for øvelser er meget gode til at få dig til at tænke algoritmisk. De ændrer også din måde at arbejde på i dit daglige job. Min anbefaling ville være at gøre det samme som jeg forsøger at gøre - træne din hjerne nu og da med en af ​​dem. Og hvis du kan - del. Jeg ved nogle gange, at du ikke har tid til sådanne udfordringer, men når du gør det - gå efter det.

Min personlige følelse efter at have afsluttet dette var total tilfredshed, hvilket er helt forståeligt i betragtning af den tid det tog mig at gøre det. Men til sidst, kære læser, jeg er endnu gladere over, at jeg kan dele denne oplevelse med dig ?!

Tak for læsningen. Læs flere af mine artikler på mihail-gaberov.eu.