Controlla se due stringhe sono anagrammi in Java

1. Panoramica

Secondo Wikipedia, un anagramma è una parola o una frase formata riorganizzando le lettere di una parola o frase diversa.

Possiamo generalizzare questo nell'elaborazione delle stringhe dicendo che un anagramma di una stringa è un'altra stringa con esattamente la stessa quantità di ogni carattere, in qualsiasi ordine .

In questo tutorial, esamineremo come rilevare anagrammi di stringhe intere in cui la quantità di ogni carattere deve essere uguale, inclusi caratteri non alfabetici come spazi e cifre. Ad esempio, "! Low-salt!" e "gufi-lat !!" sarebbero considerati anagrammi in quanto contengono esattamente gli stessi caratteri.

2. Soluzione

Confrontiamo alcune soluzioni che possono decidere se due stringhe sono anagrammi. Ogni soluzione controllerà all'inizio se le due stringhe hanno lo stesso numero di caratteri. Questo è un modo rapido per uscire in anticipo poiché gli input con lunghezze diverse non possono essere anagrammi .

Per ogni possibile soluzione, diamo un'occhiata alla complessità di implementazione per noi sviluppatori. Vedremo anche la complessità temporale per la CPU, usando la notazione O grande.

3. Verifica per ordinamento

Possiamo riorganizzare i caratteri di ciascuna stringa ordinandone i caratteri, il che produrrà due array di caratteri normalizzati.

Se due stringhe sono anagrammi, le loro forme normalizzate dovrebbero essere le stesse.

In Java, possiamo prima convertire le due stringhe in array char [] . Quindi possiamo ordinare questi due array e verificare l'uguaglianza:

boolean isAnagramSort(String string1, String string2) { if (string1.length() != string2.length()) { return false; } char[] a1 = string1.toCharArray(); char[] a2 = string2.toCharArray(); Arrays.sort(a1); Arrays.sort(a2); return Arrays.equals(a1, a2); } 

Questa soluzione è di facile comprensione e implementazione. Tuttavia, il tempo di esecuzione complessivo di questo algoritmo è O (n log n) perché l'ordinamento di un array di n caratteri richiede tempo O (n log n) .

Affinché l'algoritmo funzioni, deve creare una copia di entrambe le stringhe di input come array di caratteri, utilizzando un po 'di memoria extra.

4. Controllare contando

Una strategia alternativa è contare il numero di occorrenze di ogni carattere nei nostri input. Se questi istogrammi sono uguali tra gli input, le stringhe sono anagrammi.

Per risparmiare un po 'di memoria, costruiamo un solo istogramma. Incrementeremo il conteggio per ogni carattere nella prima stringa e diminuiremo il conteggio per ogni carattere nella seconda. Se le due stringhe sono anagrammi, il risultato sarà che tutto si bilancia a 0.

L'istogramma necessita di una tabella di conteggi di dimensioni fisse con una dimensione definita dalla dimensione del set di caratteri. Ad esempio, se utilizziamo un solo byte per memorizzare ogni carattere, possiamo utilizzare una dimensione dell'array di conteggio di 256 per contare l'occorrenza di ogni carattere:

private static int CHARACTER_RANGE= 256; public boolean isAnagramCounting(String string1, String string2) { if (string1.length() != string2.length()) { return false; } int count[] = new int[CHARACTER_RANGE]; for (int i = 0; i < string1.length(); i++) { count[string1.charAt(i)]++; count[string2.charAt(i)]--; } for (int i = 0; i < CHARACTER_RANGE; i++) { if (count[i] != 0) { return false; } } return true; }

Questa soluzione è più veloce con la complessità temporale di O (n) . Tuttavia, necessita di spazio aggiuntivo per la matrice di conteggio. A 256 numeri interi, per ASCII non è poi così male.

Tuttavia, se dobbiamo aumentare CHARACTER_RANGE per supportare set di caratteri a più byte come UTF-8, questo diventerebbe molto affamato di memoria. Pertanto, è davvero pratico solo quando il numero di caratteri possibili è in un intervallo ridotto.

Da un punto di vista dello sviluppo, questa soluzione contiene più codice da mantenere e utilizza meno le funzioni della libreria Java.

5. Verificare con MultiSet

Possiamo semplificare il processo di conteggio e confronto utilizzando MultiSet . MultiSet è una raccolta che supporta l'uguaglianza indipendente dall'ordine con elementi duplicati. Ad esempio, i multiset {a, a, b} e {a, b, a} sono uguali.

Per utilizzare Multiset , dobbiamo prima aggiungere la dipendenza Guava al nostro file pom.xml del progetto :

 com.google.guava guava 28.1-jre  

Convertiremo ciascuna delle nostre stringhe di input in un MultiSet di caratteri. Quindi controlleremo se sono uguali:

boolean isAnagramMultiset(String string1, String string2) { if (string1.length() != string2.length()) { return false; } Multiset multiset1 = HashMultiset.create(); Multiset multiset2 = HashMultiset.create(); for (int i = 0; i < string1.length(); i++) { multiset1.add(string1.charAt(i)); multiset2.add(string2.charAt(i)); } return multiset1.equals(multiset2); } 

Questo algoritmo risolve il problema in tempo O (n) senza dover dichiarare un grande array di conteggio.

È simile alla precedente soluzione di conteggio. Tuttavia, invece di utilizzare una tabella di dimensioni fisse per contare, sfruttiamo la classe MutlitSet per simulare una tabella di dimensioni variabili, con un conteggio per ogni carattere.

Il codice per questa soluzione fa un uso maggiore delle capacità di libreria di alto livello rispetto alla nostra soluzione di conteggio.

6. Anagramma basato su lettere

Gli esempi finora non aderiscono strettamente alla definizione linguistica di anagramma. Questo perché considerano i caratteri di punteggiatura parte dell'anagramma e fanno distinzione tra maiuscole e minuscole.

Adattiamo gli algoritmi per abilitare un anagramma basato su lettere. Consideriamo solo la riorganizzazione delle lettere maiuscole e minuscole, indipendentemente da altri caratteri come spazi bianchi e punteggiatura. Ad esempio, "A decimal point" e "I'm a dot in place". sarebbero anagrammi l'uno dell'altro.

Per risolvere questo problema, possiamo prima preelaborare le due stringhe di input per filtrare i caratteri indesiderati e convertire le lettere in lettere minuscole. Quindi possiamo utilizzare una delle soluzioni precedenti (ad esempio, la soluzione MultiSet ) per controllare gli anagrammi sulle stringhe elaborate:

String preprocess(String source) { return source.replaceAll("[^a-zA-Z]", "").toLowerCase(); } boolean isLetterBasedAnagramMultiset(String string1, String string2) { return isAnagramMultiset(preprocess(string1), preprocess(string2)); }

Questo approccio può essere un modo generale per risolvere tutte le varianti dei problemi degli anagrammi. Ad esempio, se vogliamo includere anche delle cifre, dobbiamo solo regolare il filtro di pre-elaborazione.

7. Conclusione

In questo articolo, abbiamo esaminato tre algoritmi per verificare se una data stringa è l'anagramma di un'altra, carattere per carattere. Per ciascuna soluzione, abbiamo discusso i compromessi tra velocità, leggibilità e dimensione della memoria richiesta.

Abbiamo anche esaminato come adattare gli algoritmi per verificare la presenza di anagrammi nel senso linguistico più tradizionale. Abbiamo ottenuto questo risultato pre-elaborando gli input in lettere minuscole.

Come sempre, il codice sorgente dell'articolo è disponibile su GitHub.