Anagrammi

Ora! Questo articolo segna l’ultima sfida di manipolazione delle stringhe in questa sezione del corso. Abbiamo fatto molta strada!

In questa sfida, consideriamo due modi per individuare gli anagrammi in JavaScript.

Che cos’è un anagramma?

Si dice che una parola è un anagramma di un’altra quando può essere formata riordinando le lettere dell’altra parola usando ogni lettera una sola volta. Es. listen è un anagramma di silent.

Diamoci da fare, eh?

Dovresti già avere il tuo ambiente di sviluppo impostato per questo corso. Aggiorna il tuo repository clonato eseguendo il comando git pull. All’interno della cartella Beginner, navigate fino alla cartella isAnagram. Il nostro lavoro per questa sfida sarà fatto qui. Assicurati di seguire il fileindex-START.js.

La sfida

Date due stringhe, scrivi un algoritmo per controllare se sono anagrammi l’uno dell’altro. Restituisci vero se superano il test e falso se non lo superano. E.g

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

Pensiero Algoritmico

Per risolvere questa sfida, scriviamo una funzione che accetti due parametri, cioè le due stringhe da confrontare.

BeginnerTailwind.com Learn Tailwind CSS from Scratch

Con la funzione, confrontiamo le due parole per vedere se contengono gli stessi caratteri usati lo stesso numero di volte. Per evitare errori, sanitizziamo la stringa sbarazzandoci così dei caratteri indesiderati e degli spazi, poiché questi non sono lettere dell’alfabeto.

Convertiamo anche tutti i caratteri in un caso di lettera comune prima di effettuare qualsiasi confronto per evitare errori dovuti a variazioni di capitalizzazione. Controllare che entrambe le parole abbiano la stessa lunghezza è anche molto importante in quanto questo è un fattore primario per un confronto valido.

Facciamo questo.

Implementazione del codice

Ora considereremo due modi per implementare la nostra soluzione seguendo la nostra logica algoritmica sopra. Essi sono:

• Confronto diretto
• Confronto mappa caratteri

Confronto diretto

In questo approccio, definiamo una funzione che accetta due parametri, cioè le due stringhe da confrontare. Poi andiamo avanti a pulire entrambe le stringhe per assicurarci che stiamo confrontando solo lettere e in un caso comune.

Pulizia della stringaPer pulire la stringa, creiamo una funzione sanitizeString. Questa funzione accetta la stringa da ripulire come parametro e poi usa i metodi .toLowerCase(), .replace(), .split(), .sort() e .join() per manipolare la stringa come mostrato di seguito:

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

Per prima cosa, convertiamo l’intera stringa in minuscolo usando il metodo .toLowerCase().

In seguito, usiamo il metodo .replace() per cercare nella stringa usando il modello di espressione regolare specificato e sostituiamo ogni carattere non alfabetico con una stringa vuota. Questo ci lascia solo lettere. Niente spazi, niente simboli!

In seguito, chiamiamo .split() per dividere la stringa in un array di caratteri.

Utilizzando il metodo .sort(), ordiniamo le lettere (elementi) all’interno dell’array in ordine alfabetico.

E infine, uniamo nuovamente l’array di lettere ordinato alfabeticamente per formare una stringa.

Questa stringa è ciò che restituiamo come stringa sanificata.

Liscio!** Giusto?

Confronto delle stringhe sanificateLa sanificazione della stringa come fatto sopra è forse la parte più complicata di questa soluzione. Poi, puliamo semplicemente le stringhe ricevute usando la funzione sanitizeString e confrontiamo i risultati. Se entrambe le stringhe corrispondono, restituiamo true a significare che passano come anagrammi. Se non corrispondono, restituiamo false che significa che non lo sono.

Vedi la soluzione completa qui sotto:

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

Uno in meno!** Diventiamo più strani! 😈**

Come vedrai, l’approccio che considereremo ora segue una procedura più graduale per risolvere il problema.

Confronto tra mappe di caratteri

In questo approccio, prima generiamo una mappa di caratteri usando la nostra funzione createCharMap.

Cos’è una mappa di caratteri?

Come usato in questo contesto, un oggetto mappa di caratteri è un oggetto che mappa ogni carattere in una stringa al numero di volte che si verifica all’interno della stringa.

Creazione della mappa dei caratteriNella nostra funzione createCharMap qui sotto, usiamo un ciclo for…of per iterare attraverso ogni carattere della stringa ricevuta.

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

Per ogni carattere, controlliamo se il carattere esiste già come proprietà nella mappa dei caratteri charMap usando il metodo .hasOwnProperty(). Se esiste, incrementiamo il suo valore e se non esiste, aggiungiamo il carattere come proprietà e impostiamo il suo valore a 1.

Alla fine, restituiamo charMap che è l’oggetto mappa dei caratteri.

Confronto delle mappe dei caratteriOra che abbiamo un modo di generare le mappe dei caratteri, il prossimo passo sarà confrontare le mappe dei caratteri per entrambe le stringhe come mostrato nella soluzione completa qui sotto:

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 }}

Nota che prima controlliamo se la lunghezza delle due stringhe è uguale. Se non lo sono, restituiamo false poiché questo è un indicatore che non possono mai essere anagrammi. Se invece lo sono, andiamo oltre per generare le loro mappe dei caratteri memorizzate come variabili stringAMap e stringBMap.

Poi, usiamo il ciclo for…in per confrontare ogni carattere e valore in stringAMap con il valore corrispondente del carattere in stringBMap. Se qualche valore non corrisponde, restituiamo false come indicazione che le stringhe non sono anagrammi. Tuttavia, se tutti i valori corrispondono, il test viene superato e restituiamo true come indicazione che le stringhe testate sono effettivamente anagrammi.

Ci siamo riusciti. Un’implementazione più lunga, ma sicuramente più esplicativa.

Eseguiamo i nostri test ora, che ne dite?

Test di correttezza con Jest

Per testare ogni soluzione di cui sopra, esegui il seguente comando dal tuo terminale:

npm run test isAnagram

• Confronto diretto

• Confronto mappa caratteri

Sembra che andiamo sempre bene! Abbiamo superato tutti i test.

Testando le prestazioni con JSPerf

Eseguiamo un test delle prestazioni per determinare quale soluzione è più veloce. Trovate uno screenshot del risultato qui sotto:

Dal risultato, osserviamo che:

L’implementazione più veloce è l’approccio Character Map Comparison e il metodo Direct Comparison anche se conciso è circa 52% più lento.

**Sorprendente, vero? Le metriche non mentono mai però!**

Applicazione pratica

Gli algoritmi esplorati sopra possono essere applicati in vari modi. Questi includono:

• Crittografia
• Generazione di password
• Trusted Time-stamping
• Codifica di interviste
• Generazione di mnemotecniche
• Giochi di parole
  

  Conclusione

Nel considerare le tecniche e i concetti sopra esplorati, abbiamo imparato preziosi modi per manipolare le stringhe al fine di determinare se sono anagrammi. Abbiamo anche esplorato varie aree in cui questa conoscenza può essere utilizzata direttamente.

Dopo aver eseguito i nostri test di performance possiamo ora concludere che l’approccio più ottimale per risolvere questo problema è il metodo Character Map Comparison.

Ulteriori letture

Per saperne di più sui concetti e le tecniche evidenziate sopra, potete usare i seguenti link:

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

Ci vediamo nella prossima serie di articoli incentrati sugli algoritmi di manipolazione degli array!✌🏿

Ti piace questo articolo? Segui @worldclassdev su Twitter