Verificare se due stringhe sono anagrammi in JavaScript

In questo articolo vediamo, passo dopo passo, come implementare in JavaScript una funzione per verificare se due stringhe sono anagrammi, cioè se contengono esattamente le stesse lettere, solo in ordine diverso. Partiremo da una definizione informale, per poi arrivare a una soluzione robusta, riutilizzabile e facilmente testabile.

Che cos'è un anagramma

Due parole o frasi sono anagrammi se, una volta rimossi spazi e segni di punteggiatura e ignorate le differenze tra maiuscole e minuscole, le lettere presenti e il numero di occorrenze di ciascuna lettera coincidono esattamente.

Ad esempio:

  • roma e amor sono anagrammi;
  • listen e silent sono anagrammi;
  • cane e cena sono anagrammi;
  • casa e cassa non sono anagrammi, perché il numero di s è diverso.

Strategia generale

Qualunque implementazione deve affrontare almeno tre aspetti:

  1. Normalizzare le stringhe (gestire spazi, punteggiatura, maiuscole/minuscole, caratteri accentati).
  2. Confrontare il contenuto delle stringhe normalizzate.
  3. Restituire un valore booleano (true o false) chiaro e prevedibile.

Le due strategie più comuni per il confronto sono:

  1. Ordinare le lettere delle due stringhe e confrontare i risultati.
  2. Contare le occorrenze di ogni carattere e confrontare le frequenze.

Vedremo entrambe, partendo dalla normalizzazione dell'input.

Normalizzare le stringhe

In quasi tutti i casi reali vogliamo una funzione di supporto che prenda una stringa e la riporti in una forma "pulita", pronta al confronto. Possiamo ad esempio:

  • convertire tutto in minuscolo;
  • rimuovere spazi e punteggiatura;
  • normalizzare gli accenti dove necessario.

Una possibile funzione di normalizzazione è la seguente. 

function normalize(str) {
  if (typeof str !== "string") {
    throw new TypeError("normalize si aspetta una stringa");
  }

  return str
    .toLowerCase()
    // normalizza caratteri accentati (es. "è" -> "e")
    .normalize("NFD")
    .replace(/[̀-ͯ]/g, "")
    // tiene solo lettere (a-z) e numeri, rimuovendo spazi e punteggiatura
    .replace(/[^a-z0-9]/g, "");
}

Qui utilizziamo String.prototype.normalize con la forma NFD per separare i caratteri base dai segni diacritici, e poi rimuoviamo questi ultimi tramite una espressione regolare. Infine, limitiamo la stringa a lettere ASCII e cifre.

Approccio 1: ordinare i caratteri

L'idea è semplice:

  1. normalizziamo entrambe le stringhe;
  2. se la lunghezza è diversa, non possono essere anagrammi;
  3. ordiniamo i caratteri delle due stringhe;
  4. confrontiamo le stringhe ordinate.
function areAnagramsBySorting(a, b) {
  const normA = normalize(a);
  const normB = normalize(b);

  if (normA.length !== normB.length) {
    return false;
  }

  const sortedA = normA.split("").sort().join("");
  const sortedB = normB.split("").sort().join("");

  return sortedA === sortedB;
}

// Esempi d'uso
console.log(areAnagramsBySorting("Roma", "Amor"));      // true
console.log(areAnagramsBySorting("Cane", "Cena"));      // true
console.log(areAnagramsBySorting("casa", "cassa"));     // false
console.log(areAnagramsBySorting("Listen", "Silent")); // true

Analisi della complessità

Supponiamo che la lunghezza della stringa normalizzata sia n (per semplicità assumiamo che entrambe abbiano la stessa lunghezza). Ordinare un array di n elementi costa tipicamente O(n log n). La normalizzazione e la comparazione linea per linea costano O(n). Complessivamente, quindi, questo approccio ha complessità temporale O(n log n).

Approccio 2: contare le occorrenze dei caratteri

Invece di ordinare i caratteri, possiamo contare quante volte compare ogni carattere in ciascuna stringa normalizzata. Se le frequenze coincidono per tutti i caratteri, le stringhe sono anagrammi.

Costruire una mappa di frequenze

Useremo un semplice "contatore" sotto forma di oggetto JavaScript. 

function buildCharFrequencyMap(str) {
  const map = {};

  for (const char of str) {
    map[char] = (map[char] || 0) + 1;
  }

  return map;
}

Ora possiamo definire la funzione principale che usa le mappe di frequenza. 

function areAnagramsByCounting(a, b) {
  const normA = normalize(a);
  const normB = normalize(b);

  if (normA.length !== normB.length) {
    return false;
  }

  const freqA = buildCharFrequencyMap(normA);
  const freqB = buildCharFrequencyMap(normB);

  // Confronto delle frequenze
  for (const char in freqA) {
    if (freqA[char] !== freqB[char]) {
      return false;
    }
  }

  return true;
}

// Esempi d'uso
console.log(areAnagramsByCounting("Roma", "Amor"));      // true
console.log(areAnagramsByCounting("Cane", "Cena"));      // true
console.log(areAnagramsByCounting("casa", "cassa"));     // false
console.log(areAnagramsByCounting("Listen", "Silent")); // true

Analisi della complessità

Costruire la mappa di frequenza richiede un passaggio lineare sulla stringa, quindi O(n). Il confronto delle mappe è proporzionale al numero di caratteri distinti, che nel caso peggiore è al più n, quindi ancora O(n). Nel complesso, questo approccio ha complessità temporale O(n), che è asintoticamente migliore rispetto all'approccio basato sull'ordinamento.

Gestione di input non validi o casi limite

Nella pratica potrebbe essere utile gestire anche casi non standard:

  • valori null o undefined;
  • stringhe vuote;
  • tipi diversi da string (numeri, oggetti, ecc.).

Possiamo modificare leggermente la nostra funzione per renderla più robusta. 

function areAnagrams(a, b) {
  // Consideriamo due valori null/undefined come non anagrammi
  if (typeof a !== "string" || typeof b !== "string") {
    return false;
  }

  const normA = normalize(a);
  const normB = normalize(b);

  if (normA.length === 0 && normB.length === 0) {
    // a scelta: potremmo decidere che due stringhe vuote sono anagrammi
    return true;
  }

  if (normA.length !== normB.length) {
    return false;
  }

  const freq = {};

  // Incrementiamo i contatori per la prima stringa
  for (const char of normA) {
    freq[char] = (freq[char] || 0) + 1;
  }

  // Decrementiamo per la seconda; se qualcosa non torna restituiamo false
  for (const char of normB) {
    if (!freq[char]) {
      return false;
    }
    freq[char] -= 1;
  }

  // Se tutti i contatori sono tornati a zero, sono anagrammi
  return true;
}

In questa versione usiamo una singola mappa di frequenze: incrementiamo i contatori per la prima stringa e li decrementiamo per la seconda. Se durante il decremento troviamo un carattere non presente o che scende sotto zero, sappiamo che le stringhe non sono anagrammi.

Confronto tra i due approcci

In sintesi:

  • Approccio con ordinamento
    Più semplice e spesso sufficiente per stringhe corte o per esempi didattici, ma con complessità O(n log n) per via dell'ordinamento.
  • Approccio con conteggio delle occorrenze
    Richiede qualche riga di codice in più, ma è più efficiente dal punto di vista asintotico (O(n)) e scala meglio con stringhe molto lunghe.

Conclusioni

Abbiamo visto come realizzare in JavaScript una funzione per verificare se due stringhe sono anagrammi, partendo dalla normalizzazione dell'input e arrivando a due diverse strategie di confronto. In contesti reali è importante adottare una funzione di normalizzazione adeguata al dominio dell'applicazione (ad esempio, lingua, set di caratteri accettati, sensibilità agli spazi) e scegliere l'approccio più adatto in termini di semplicità e prestazioni.

La funzione areAnagrams mostrata sopra rappresenta una base solida e facilmente estendibile per la maggior parte degli scenari comuni.

Torna su