Această postare vă va ajuta să găsiți soluția mea la o provocare de codare numită „Sherlock și Anagramele”. Poate aruncați o privire în el HackerRank.

Am petrecut mult timp încercând să o rezolv, cu JavaScript. Când am încercat să o fac pe Google, nu am putut găsi o soluție decentă JS. Am găsit doar unul și nu funcționa corect. De asemenea, orice explicație a fost complet exclusă. De aceea am decis să scriu un articol despre asta și să încerc să pun câteva explicații frumoase și ușor de digerat pe parcurs. Continuați să citiți acum!

⚠️ ATENȚIE: Voi lansa soluția mea mai jos, cu scurte explicații despre fiecare dintre pași. Dacă doriți să încercați singur, vă rugăm să vă opriți aici și accesați site-ul HackerRank.

Problemă

Două corzi sunt anagramele între ele dacă literele unui șir pot fi rearanjate pentru a forma celălalt șir. Având în vedere un șir, găsiți numărul de perechi de șiruri de caractere ale șirului care sunt anagrama una față de alta.

Citește mai multCum se face o promisiune dintr-o funcție de apel invers în JavaScript

De exemplu s = mama, lista tuturor perechilor anagrammatice este [m, m], [mo, om] la poziții [[0], [2]] [[0, 1], [1, 2]]respectiv.

Constrângeri
Lungimea șirului de intrare: 2 ≤ | s | ≤ 100
Şir s conține doar litere mici din gama ascii[a-z].

Analiză

În primul rând, trebuie să înțelegem mai bine întreaga problemă. Ce este o anagramă? Ce este o pereche anagrammatică? Pot vedea unul? De asemenea, ce înseamnă exact asta șiruri de caractere?

Cu alte cuvinte, trebuie să avem o imagine clară a ceea ce încercăm să rezolvăm, înainte de a o rezolva.

Din descrierea problemei, putem deduce tot ce avem nevoie. Continuă să mergi! ?

Citește mai multCum se generează un fișier de reducere GitHub din Microsoft Word utilizând TypeScript

Cred că acesta este un moment bun pentru a menționa că provocarea în cauză se află în secțiunea „Dicționare și Hashmaps” de pe site-ul HackerRank. Probabil că veți crede că ar trebui să utilizați acest tip de structură de date atunci când o rezolvați. ?

Anagramele

Deoarece vom căuta anagramele, să începem cu ele. După cum este descris mai sus, o anagramă a unui cuvânt este un alt cuvânt care are aceeași lungime și este creat cu aceleași caractere din cuvântul anterior.

Cum se rezolva provocarea de codare Sherlock si Anagrams in
Animație pentru anagrama „Ascultă = Silențios”

Deci va trebui să căutăm cuvinte și să le comparăm cu alte cuvinte, pentru a vedea dacă sunt perechi anagrammatice. Odată găsite, le vom număra.

Perechi anagrammatice

Deoarece am văzut ce este o anagramă, ar trebui să fie relativ ușor să concluzionăm că o pereche anagrammatică este doar două șiruri care sunt anagrame. Cum ar fi „mo” și „om”, sau „ascultă” și „tăcut”. Va trebui să numărăm câte perechi de acest gen pot fi găsite într-un șir dat. Pentru a face acest lucru, trebuie să împărțim acest șir original în șiruri de caractere.

Substrings

Șirurile, așa cum se deduce numele, sunt părți ale unui șir. Aceste părți ar putea fi doar o literă sau o pereche de litere, cum ar fi ceea ce am văzut în exemplul de mai sus – „m”Sau„mo.”În soluția noastră, vom împărți șirul original la astfel de șiruri de caractere și apoi vom trece peste ele și vom face comparația, ceea ce ne va spune dacă avem perechi anagrammatice printre ele.

Soluţie

Citește mai multAutentificare utilizând Google în ASP.NET Core 2.0

Acum, după ce ne-am făcut analiza, este ora spectacolului! ?

Să rezumăm:

  1. Trebuie să găsim toate șirurile de caractere ale șirului dat – creați o metodă pentru asta.
  2. Trebuie să putem verifica dacă două șiruri sunt anagrame – creați o metodă pentru asta.
  3. Trebuie să numărăm toate perechile anagrammatice din șirul dat – creați o metodă pentru asta.
  4. Combină totul de sus și scuipă rezultatul – creează o metodă pentru asta.

Obțineți toate șirurile

Aceasta va fi metoda noastră de ajutor pentru găsirea tuturor șirurilor de caractere ale unui șir dat:

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
}

După cum puteți vedea, are o complexitate de timp O (n²). Pentru cazul nostru, face treaba, deoarece avem o lungime limitată a șirului de intrare (până la 100 de caractere).

Căutați anagramele

Aceasta va fi metoda noastră de ajutor pentru a verifica dacă două șiruri sunt perechi anagrammatice:

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
}

Amintiți-vă că am presupus că cel mai probabil va trebui să folosim structuri de date cum ar fi hashmaps sau dicționare (având în vedere secțiunea în care această provocare se găsește pe HackerRank).

Folosim un obiect JavaScript simplu pentru a juca rolul unui hashmap. Facem două iterații – una pe șir. Când iterăm peste primul, îi adăugăm caracterele ca chei la hashmap și le numărăm aparițiile, care vor fi stocate ca valori ale acestora. Apoi facem o altă iterație peste al doilea șir. Verificați dacă caracterele sale sunt stocate în hashmap-ul nostru. Dacă da – diminuați valoarea lor. Dacă lipsesc caractere, ceea ce înseamnă că cele două șiruri nu sunt o pereche anagrammatică, returnăm pur și simplu false. Dacă ambele bucle sunt complete, vom reveni la adevărat, ceea ce înseamnă că șirurile analizate sunt o pereche anagrammatică.

Faceți numărarea

Aceasta este metoda, în care vom folosi ajutorul pentru a verifica dacă o pereche este anagrammatică și o vom număra. Facem acest lucru cu ajutorul matricelor JavaScript și a metodelor pe care le furnizează. Iterăm pe o matrice care conține toate șirurile de caractere ale șirului original. Apoi obținem elementul corect și îl eliminăm din matrice. Și apoi facem o altă buclă prin acea matrice și returnăm 1 dacă descoperim că există o anagramă a elementului curent. Dacă nu se găsește nimic, returnăm 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
}

Si in sfarsit

Singurul lucru care rămâne de făcut acum este să combinați toate cele de mai sus și să scuipa rezultatul dorit. Iată cum arată metoda finală:

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
}

Poate că ați observat, aici verific mai întâi duplicatele pentru a ști dacă ar trebui să continui mai departe. De parcă nu există litere duplicate, atunci nu este posibil să aveți o anagramă.

Și, în sfârșit, obținem toate șirurile într-o matrice, iterăm peste acesta, numărăm perechile anagrammatice care se găsesc și returnăm acest număr.

Puteți găsi codul complet Aici.

Concluzie

Acest gen de exerciții sunt foarte bune pentru a vă face să gândiți algoritmic. De asemenea, îți schimbă modul de lucru în munca ta de zi cu zi. Recomandarea mea ar fi să fac același lucru pe care încerc să îl fac – antrenează-ți creierul din când în când cu unul dintre acestea. Și dacă poți – împărtășește. Știu că uneori nu ai timp pentru astfel de provocări, dar când o ai – mergi pentru asta.

Sentimentul meu personal după ce am terminat acest lucru a fost o satisfacție totală, ceea ce este complet de înțeles, având în vedere timpul pe care mi-a luat-o să o fac. Dar, în cele din urmă, dragă cititoare, sunt și mai fericit că pot să vă împărtășesc această experiență ?!

Mulțumesc pentru lectură. Citiți mai multe din articolele mele la mihail-gaberov.eu.