Anagrame

Hooray! Acest articol marchează ultima probă de manipulare a șirurilor de caractere din această secțiune a cursului. Am parcurs un drum lung!

În această provocare, luăm în considerare două moduri de a detecta anagramele în JavaScript.

Ce este o anagramă?

Se spune că un cuvânt este o anagramă a altuia atunci când poate fi format prin rearanjarea literelor celuilalt cuvânt folosind fiecare literă doar o singură dată. De exemplu, listen este o anagramă a silent.

Să ne apucăm de treabă, da?

Ar trebui să aveți deja configurat mediul de dezvoltare pentru acest curs. Actualizați depozitul clonat prin rularea comenzii git pull. În interiorul folderului Beginner, navigați la folderul isAnagram. Munca noastră pentru această provocare se va face aici. Asigurați-vă că urmăriți în fișierulindex-START.js.

Provocarea

Date două șiruri de caractere, scrieți un algoritm pentru a verifica dacă acestea sunt anagrame una față de cealaltă. Returnați true dacă trec testul și false dacă nu. E.g

isAnagram('silent', 'listen') // should return true

Gândire algoritmică

În rezolvarea acestei provocări, scriem o funcție care să accepte doi parametri, adică cele două șiruri de comparat.

BeginnerTailwind.com Learn Tailwind CSS from Scratch

În cadrul funcției, comparăm cele două cuvinte pentru a vedea dacă ele conțin aceleași caractere folosite de același număr de ori. Pentru a evita erorile, igienizăm șirul eliminând astfel caracterele nedorite și spațiile, deoarece acestea nu sunt litere ale alfabetului.

De asemenea, convertim toate caracterele la o majusculă comună înainte de a efectua orice comparație pentru a evita erorile datorate variației majusculelor. Verificarea faptului că ambele cuvinte au aceeași lungime este, de asemenea, foarte importantă, deoarece acesta este un factor principal pentru o comparație validă.

Să facem acest lucru.

Implementarea codului

Acum vom lua în considerare două moduri de a implementa soluția noastră urmând logica noastră algoritmică de mai sus. Acestea sunt:

• Comparare directă
• Comparare pe hartă de caractere

Comparare directă

În această abordare, definim o funcție care acceptă doi parametri, adică cele două șiruri de caractere care urmează să fie comparate. Apoi trecem la curățarea ambelor șiruri pentru a ne asigura că se compară numai litere și într-o majusculă comună.

Curățarea șirului Pentru a curăța șirul, creăm o funcție sanitizeString. Această funcție acceptă șirul care trebuie curățat ca parametru și folosește metodele .toLowerCase(), .replace(), .split(), .sort() și .join() pentru a manipula șirul, după cum se arată mai jos:

const sanitizeString = function (str) { return str.toLowerCase().replace(//g, '').split('').sort().join('');}

Să împărțim puțin lucrurile:

• În primul rând, convertim întregul șir în minuscule folosind metoda .toLowerCase().
• În continuare, folosim metoda .replace() pentru a căuta în șir folosind modelul de expresie regulată specificat și înlocuim fiecare caracter care nu este alfabetic cu un șir gol. Astfel rămânem doar cu litere. Fără spații, fără simboluri!
• În continuare, apelăm .split() pentru a împărți șirul într-o matrice de caractere.
• Utilizând metoda .sort(), sortăm literele (elementele) din cadrul matricei în ordine alfabetică.
• Și, în cele din urmă, unim din nou matricea de litere, acum ordonată alfabetic, pentru a forma din nou un șir de caractere.

Acest șir de caractere este ceea ce returnăm ca șir de caractere salubrizat.

Limpede!** Corect?**

Compararea șirurilor salubrizateSalubrizarea șirului de caractere, așa cum s-a făcut mai sus, este poate cea mai dificilă parte a acestei soluții. În continuare, vom curăța pur și simplu șirurile primite cu ajutorul funcției sanitizeString și vom compara rezultatele. În cazul în care ambele șiruri se potrivesc, returnăm true semnificând că acestea trec drept anagrame. Dacă nu se potrivesc, returnăm false semnificând că nu sunt.

Vezi soluția completă mai jos:

function isAnagram(stringA, stringB) { const sanitizeString = function (str) { return str.toLowerCase().replace(//g, '').split('').sort().join(''); } return sanitizeString(stringA) == sanitizeString(stringB)}

Unul jos!** Să devenim mai ciudați! 😈**

După cum veți vedea, abordarea pe care o vom lua în considerare acum urmează o procedură mai pas cu pas pentru rezolvarea problemei.

Compararea hărților de caractere

În această abordare, generăm mai întâi o hartă de caractere folosind funcția noastră createCharMap.

Ce este o hartă de caractere?

Așa cum este folosit în acest context , un obiect hartă de caractere este un obiect care mapează fiecare caracter dintr-un șir de caractere cu numărul de ori de câte ori apare în cadrul șirului.

Crearea hărții de caractereÎn funcția noastră createCharMap de mai jos, folosim o buclă for…of pentru a parcurge fiecare caracter din șirul primit.

function createCharMap(text) { let charMap = {} for (let char of text) { if (charMap.hasOwnProperty(char)) { charMap++ } else { charMap = 1 } } return charMap}

Pentru fiecare caracter, verificăm dacă acesta există deja ca o proprietate în harta de caractere charMap folosind metoda .hasOwnProperty(). Dacă există, îi creștem valoarea, iar dacă nu există, adăugăm caracterul ca proprietate și îi stabilim valoarea la 1.

În final, returnămcharMapcare este obiectul hartă de caractere.

Compararea hărților de caractereAcum că avem o modalitate de generare a hărților de caractere, următorul pas va fi compararea hărților de caractere pentru ambele șiruri de caractere, așa cum se arată în soluția completă de mai jos:

function isAnagram(stringA, stringB) { function createCharMap(text) { let charMap = {} for (let char of text) { if (charMap.hasOwnProperty(char)) { charMap++ } else { charMap = 1 } } return charMap } if (stringA.length === stringB.length) { let stringAMap = createCharMap(stringA) let stringBMap = createCharMap(stringB) for (let char in stringAMap) { if (stringAMap !== stringBMap) { return false } } return true } else { return false }}

Observați că mai întâi verificăm dacă lungimea ambelor șiruri de caractere este egală. Dacă nu sunt, returnăm false, deoarece acesta este un indicator că ele nu pot fi niciodată anagrame. Dacă totuși sunt, mergem mai departe pentru a genera hărțile lor de caractere stocate ca variabile stringAMap și stringBMap.

În continuare, folosim bucla for…in pentru a compara fiecare caracter și valoare din stringAMap cu valoarea corespunzătoare caracterului din stringBMap. Dacă există valori care nu se potrivesc, returnăm false ca o indicație că șirurile nu sunt anagrame. Cu toate acestea, dacă toate valorile se potrivesc, testul este trecut și returnăm true ca o indicație că șirurile testate sunt într-adevăr anagrame.

Am reușit. O implementare mai lungă, într-adevăr, dar este cu siguranță una mai explicativă.

Să rulăm testele noastre acum, da?

Testarea corectitudinii cu Jest

Pentru a testa fiecare soluție de mai sus, rulați următoarea comandă din terminalul dumneavoastră:

npm run test isAnagram

• Comparare directă

• Comparare pe hartă de caractere

Se pare că întotdeauna ne descurcăm de minune! Am trecut toate testele.

Testarea performanțelor cu JSPerf

Aici, executăm un test de performanță pentru a determina care soluție este mai rapidă. Găsiți mai jos o captură de ecran a rezultatului:

Din rezultat, observăm că:

Implementarea mai rapidă este abordarea Character Map Comparison și metoda Direct Comparison deși concisă este cu aproximativ 52% mai lentă.

**Surprinzător, nu-i așa? Totuși, metricile nu mint niciodată!**

Aplicație practică

Agoritmii explorați mai sus pot fi aplicați în diverse moduri. Acestea includ:

• Criptare
• Generarea de parole
• Înregistrarea timpului de încredere
• Codarea interviurilor
• Generarea de mnemotehnici
• Jocuri de cuvinte
  

  Concluzie

În timp ce luăm în considerare tehnicile și conceptele explorate mai sus, am învățat modalități valoroase de a manipula șiruri de caractere pentru a determina dacă acestea sunt anagrame. De asemenea, am explorat diverse domenii în care aceste cunoștințe pot fi utilizate în mod direct.

După efectuarea testelor noastre de performanță, putem concluziona acum că cea mai optimă abordare pentru rezolvarea acestei probleme este metoda de comparare a hărților de caractere.

Lecturi suplimentare

Pentru a afla mai multe despre conceptele și tehnicile evidențiate mai sus, puteți utiliza următoarele link-uri:

• Expresii regulate
• .replace()
• .split()
• .sort()
• .join()
• .hasOwnProperty()
• For…of vs for…in loop

Ne vedem în următorul set de articole axate pe algoritmi de manipulare a array-urilor!✌🏿

Vă place acest articol? Urmăriți @worldclassdev pe Twitter

.