Rimozione di caratteri ripetuti da una stringa

1. Panoramica

In questo tutorial, discuteremo diverse tecniche in Java su come rimuovere i caratteri ripetuti da una stringa.

Per ogni tecnica, parleremo anche brevemente della sua complessità temporale e spaziale.

2. Utilizzando distinto

Iniziamo rimuovendo i duplicati dalla nostra stringa utilizzando il metodo distinto introdotto in Java 8.

Di seguito, stiamo ottenendo un'istanza di un Int S tream da un dato oggetto stringa. Quindi, stiamo usando il metodo distinto per rimuovere i duplicati. Infine, stiamo chiamando il metodo forEach per scorrere i caratteri distinti e aggiungerli al nostro StringBuilder :

StringBuilder sb = new StringBuilder(); str.chars().distinct().forEach(c -> sb.append((char) c));

Complessità temporale: O (n) - il tempo di esecuzione del loop è direttamente proporzionale alla dimensione della stringa di input

Spazio ausiliario: O (n) - poiché distinto utilizza internamente un LinkedHashSet e stiamo anche memorizzando la stringa risultante in un oggetto StringBuilder

Mantiene l'ordine: Sì, poiché LinkedHashSet mantiene l'ordine dei suoi elementi

E, sebbene sia bello che Java 8 svolga questo compito così bene per noi, confrontiamolo con gli sforzi per eseguire il nostro.

3. Utilizzando indexOf

L'approccio ingenuo alla rimozione dei duplicati da una stringa implica semplicemente il loop sull'input e l'utilizzo del metodo indexOf per verificare se il carattere corrente esiste già nella stringa risultante :

StringBuilder sb = new StringBuilder(); int idx; for (int i = 0; i < str.length(); i++) { char c = str.charAt(i); idx = str.indexOf(c, i + 1); if (idx == -1) { sb.append(c); } } 

Complessità temporale: O (n * n) : per ogni carattere, il metodo indexOf esegue la stringa rimanente

Spazio ausiliario: O (n) - è richiesto uno spazio lineare poiché utilizziamo StringBuilder per memorizzare il risultato

Mantiene l'ordine:

Questo metodo ha la stessa complessità spaziale del primo approccio, ma è molto più lento.

4. Utilizzo di una matrice di caratteri

Possiamo anche rimuovere i duplicati dalla nostra stringa convertendola in un array di caratteri e quindi eseguendo un ciclo su ciascun carattere e confrontandolo con tutti i caratteri successivi .

Come possiamo vedere di seguito, stiamo creando due cicli for e stiamo controllando se ogni elemento viene ripetuto nella stringa. Se viene trovato un duplicato, non lo aggiungiamo a StringBuilder :

char[] chars = str.toCharArray(); StringBuilder sb = new StringBuilder(); boolean repeatedChar; for (int i = 0; i < chars.length; i++) { repeatedChar = false; for (int j = i + 1; j < chars.length; j++) { if (chars[i] == chars[j]) { repeatedChar = true; break; } } if (!repeatedChar) { sb.append(chars[i]); } } 

Complessità temporale: O (n * n) - abbiamo un ciclo interno e uno esterno che attraversano entrambi la stringa di input

Spazio ausiliario: O (n) - è richiesto uno spazio lineare poiché la variabile chars memorizza una nuova copia della stringa di input e stiamo anche utilizzando StringBuilder per salvare il risultato

Mantiene l'ordine:

Ancora una volta, il nostro secondo tentativo si comporta male rispetto all'offerta Core Java, ma vediamo dove arriviamo con il nostro prossimo tentativo.

5. Utilizzo dell'ordinamento

In alternativa, i caratteri ripetuti possono essere eliminati ordinando la nostra stringa di input per raggruppare i duplicati. Per fare ciò, dobbiamo convertire la stringa in un char a rray e ordinarla usando gli array . metodo di ordinamento . Infine, itereremo sull'array di caratteri ordinato .

Durante ogni iterazione, confronteremo ogni elemento dell'array con l'elemento precedente. Se gli elementi sono diversi, aggiungeremo il carattere corrente a StringBuilder:

StringBuilder sb = new StringBuilder(); if(!str.isEmpty()) { char[] chars = str.toCharArray(); Arrays.sort(chars); sb.append(chars[0]); for (int i = 1; i < chars.length; i++) { if (chars[i] != chars[i - 1]) { sb.append(chars[i]); } } }

Complessità temporale: O (n log n) - l'ordinamento utilizza un Quicksort dual-pivot che offre prestazioni O (n log n) su molti set di dati

Spazio ausiliario: O (n) - poiché il metodo toCharArray crea una copia della stringa di input

Mantiene l'ordine: no

Riproviamo con il nostro ultimo tentativo.

6. Utilizzo di un set

Un altro modo per rimuovere i caratteri ripetuti da una stringa è attraverso l'uso di un Set . Se non ci interessa l'ordine dei caratteri nella nostra stringa di output, possiamo usare un HashSet . Altrimenti, possiamo utilizzare un LinkedHashSet per mantenere l'ordine di inserzione.

In entrambi i casi, eseguiremo un ciclo sulla stringa di input e aggiungeremo ogni carattere al Set . Una volta inseriti i caratteri nel set, eseguiremo un'iterazione su di esso per aggiungerli a StringBuilder e restituire la stringa risultante:

StringBuilder sb = new StringBuilder(); Set linkedHashSet = new LinkedHashSet(); for (int i = 0; i < str.length(); i++) { linkedHashSet.add(str.charAt(i)); } for (Character c : linkedHashSet) { sb.append(c); } 

Complessità temporale: O (n) - il tempo di esecuzione del loop è direttamente proporzionale alla dimensione della stringa di input

Spazio ausiliario: O (n) - lo spazio richiesto per il Set dipende dalla dimensione della stringa di input; inoltre, stiamo usando StringBuilder per memorizzare il risultato

Mantiene l'ordine: LinkedHashSet - Sì, HashSet - No

E ora, abbiamo abbinato l'approccio Core Java! Non è molto scioccante scoprire che questo è molto simile a ciò che già fa distinto .

7. Conclusione

In questo articolo, abbiamo coperto alcuni modi per rimuovere i caratteri ripetuti da una stringa in Java. Abbiamo anche esaminato la complessità temporale e spaziale di ciascuno di questi metodi.

Come sempre, gli snippet di codice possono essere trovati su GitHub.