Java >> Java tutorial >  >> Tag >> char

Fjernelse af gentagne tegn fra en streng

char

1. Oversigt

I denne øvelse vil vi diskutere flere teknikker i Java til, hvordan man fjerner gentagne tegn fra en streng.

For hver teknik taler vi også kort om dens kompleksitet i tid og rum.

2. Bruger distinct

Lad os starte med at fjerne dubletterne fra vores streng ved hjælp af distinkt metode introduceret i Java 8.

Nedenfor får vi en forekomst af en Int S tream fra et givent strengobjekt. Så bruger vi distinkt metode til at fjerne dubletterne. Endelig kalder vi forEach metode til at sløjfe over de distinkte tegn og tilføje dem til vores StringBuilder :

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

Tidskompleksitet:  O(n) – løkkens køretid er direkte proportional med størrelsen af ​​inputstrengen

Auxiliary Space: O(n) – siden særskilt bruger et LinkedHashSet internt, og vi gemmer også den resulterende streng i en StringBuilder objekt

Opretholder orden: Ja – siden LinkedHashSet  bevarer rækkefølgen af ​​sine elementer

Og selvom det er rart, at Java 8 klarer denne opgave så godt for os, så lad os sammenligne det med bestræbelser på at rulle vores egen.

3. Bruger indexOf

Den naive tilgang til at fjerne dubletter fra en streng involverer simpelthen løkke over inputtet og bruge indexOf metode til at kontrollere, om det aktuelle tegn allerede findes i den resulterende streng :

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

Tidskompleksitet:  O(n * n) – for hvert tegn, indexOf metoden løber gennem den resterende streng

Auxiliary Space: O(n) – lineært mellemrum er påkrævet, da vi bruger StringBuilder for at gemme resultatet

Opretholder orden: Ja

Denne metode har samme pladskompleksitet som den første tilgang, men virker meget langsommere.

4. Brug af et tegnarray

Vi kan også fjerne dubletter fra vores streng ved at konvertere den til en char array og derefter sløjfe over hvert tegn og sammenligne det med alle efterfølgende tegn .

Som vi kan se nedenfor, opretter vi to for loops, og vi tjekker, om hvert element gentages i strengen. Hvis der findes en dublet, føjer vi den ikke til 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]);
    }
}

Tidskompleksitet:  O(n * n) – vi har en indre og en ydre sløjfe, der begge krydser inputstrengen

Auxiliary Space: O(n) – lineært mellemrum er påkrævet, da tegnene variabel gemmer en ny kopi af strenginputtet, og vi bruger også StringBuilder for at gemme resultatet

Opretholder orden: Ja

Igen, vores andet forsøg klarer sig dårligt sammenlignet med Core Java-tilbuddet, men lad os se, hvor vi kommer hen med vores næste forsøg.

5. Brug af sortering

Alternativt kan gentagne tegn elimineres ved at sortere vores inputstreng for at gruppere dubletter. For at gøre det skal vi konvertere strengen til en char a rray og sorter det ved hjælp af Arrays .sortér metode. Til sidst gentager vi den sorterede char array.

Under hver iteration vil vi sammenligne hvert element i arrayet med det forrige element. Hvis elementerne er forskellige, føjer vi det aktuelle tegn til 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]);
        }
    }
}

Tidskompleksitet:  O(n log n) – sorteringen bruger en Quicksort med dobbelt pivot, som tilbyder O(n log n) ydeevne på mange datasæt

Auxiliary Space: O(n) – siden toCharArray metode laver en kopi af input String

Opretholder orden: Nej

Lad os prøve det igen med vores sidste forsøg.

6. Brug af et Set

En anden måde at fjerne gentagne tegn fra en streng på er ved at bruge et Set . Hvis vi er ligeglade med rækkefølgen af ​​tegn i vores outputstreng, kan vi bruge et HashSet . Ellers kan vi bruge et LinkedHashSet  for at opretholde indsættelsesrækkefølgen.

I begge tilfælde vil vi sløjfe over inputstrengen og tilføje hvert tegn til Sættet . Når tegnene er indsat i sættet, gentager vi det for at tilføje dem til StringBuilder  og returner den resulterende streng:

StringBuilder sb = new StringBuilder();
Set<Character> linkedHashSet = new LinkedHashSet<>();

for (int i = 0; i < str.length(); i++) {
    linkedHashSet.add(str.charAt(i));
}

for (Character c : linkedHashSet) {
    sb.append(c);
}

Tidskompleksitet:  O(n) – løkkens køretid er direkte proportional med størrelsen af ​​inputstrengen

Auxiliary Space: O(n) – der kræves plads til sættet afhænger af størrelsen på inputstrengen; Vi bruger også StringBuilder for at gemme resultatet

Opretholder orden: LinkedHashSet –  Ja, HashSet  – Nej

Og nu har vi matchet Core Java-tilgangen! Det er ikke særlig chokerende at finde ud af, at dette minder meget om det distinkte allerede gør.

7. Konklusion

I denne artikel dækkede vi et par måder at fjerne gentagne tegn fra en streng i Java. Vi så også på kompleksiteten af ​​tid og rum for hver af disse metoder.

Som altid kan kodestykker findes over på GitHub.


Java tag