Menghapus Karakter Berulang dari String

1. Ikhtisar

Dalam tutorial ini, kita akan membahas beberapa teknik di Java tentang cara menghapus karakter berulang dari sebuah string.

Untuk setiap teknik, kita juga akan membahas secara singkat tentang kompleksitas ruang dan waktu.

2. Menggunakan berbeda

Mari kita mulai dengan menghapus duplikat dari string kita menggunakan metode berbeda yang diperkenalkan di Java 8.

Di bawah ini, kita mendapatkan sebuah contoh dari Int S tream dari objek string yang diberikan. Kemudian, kami menggunakan metode berbeda untuk menghapus duplikat. Terakhir, kami memanggil metode forEach untuk mengulang karakter yang berbeda dan menambahkannya ke StringBuilder kami :

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

Kompleksitas Waktu: O (n) - runtime loop berbanding lurus dengan ukuran string input

Ruang Bantu: O (n) - karena perbedaan menggunakan LinkedHashSet secara internal dan kami juga menyimpan string yang dihasilkan dalam objek StringBuilder

Pertahankan Urutan: Ya - karena LinkedHashSet mempertahankan urutan elemennya

Dan, meskipun bagus bahwa Java 8 melakukan tugas ini untuk kita dengan sangat baik, mari kita bandingkan dengan upaya untuk menggulirnya sendiri.

3. Menggunakan indexOf

Pendekatan naif untuk menghapus duplikat dari string hanya melibatkan pengulangan input dan menggunakan metode indexOf untuk memeriksa apakah karakter saat ini sudah ada dalam string yang dihasilkan :

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

Kompleksitas Waktu: O (n * n) - untuk setiap karakter, metode indexOf berjalan melalui string yang tersisa

Ruang Bantu: O (n) - ruang linier diperlukan karena kita menggunakan StringBuilder untuk menyimpan hasilnya

Mempertahankan Urutan: Ya

Metode ini memiliki kompleksitas ruang yang sama dengan pendekatan pertama tetapi kinerjanya jauh lebih lambat.

4. Menggunakan Array Karakter

Kami juga dapat menghapus duplikat dari string kami dengan mengubahnya menjadi array karakter dan kemudian mengulang setiap karakter dan membandingkannya dengan semua karakter berikutnya .

Seperti yang bisa kita lihat di bawah, kita membuat dua loop for dan kita memeriksa apakah setiap elemen diulang dalam string. Jika duplikat ditemukan, kami tidak menambahkannya ke 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]); } } 

Kompleksitas Waktu: O (n * n) - kita memiliki loop dalam dan luar yang melintasi string input

Ruang Bantu: O (n) - ruang linier diperlukan karena variabel chars menyimpan salinan baru dari input string dan kami juga menggunakan StringBuilder untuk menyimpan hasilnya

Mempertahankan Urutan: Ya

Sekali lagi, upaya kedua kami berkinerja buruk dibandingkan dengan penawaran Core Java, tetapi mari kita lihat di mana kami mendapatkan upaya kami berikutnya.

5. Menggunakan Sorting

Atau, karakter berulang dapat dihilangkan dengan mengurutkan string input kami ke duplikat grup. Untuk melakukan itu, kita harus mengubah string menjadi char a rray dan mengurutkannya menggunakan Array . metode sortir . Akhirnya, kita akan mengulangi array karakter yang diurutkan .

Selama setiap iterasi, kita akan membandingkan setiap elemen dari array dengan elemen sebelumnya. Jika elemennya berbeda maka kami akan menambahkan karakter saat ini ke 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]); } } }

Kompleksitas Waktu: O (n log n) - pengurutan menggunakan Quicksort pivot ganda yang menawarkan kinerja O (n log n) pada banyak kumpulan data

Ruang Bantu: O (n) - karena metode toCharArray membuat salinan dari Input String

Mempertahankan Urutan: Tidak

Mari kita coba lagi dengan upaya terakhir kita.

6. Menggunakan Set

Another way to remove repeated characters from a string is through the use of a Set. If we do not care about the order of characters in our output string we can use a HashSet.Otherwise, we can use a LinkedHashSet to maintain the insertion order.

In both cases, we'll loop over the input string and add each character to the Set. Once the characters are inserted into the set, we'll iterate over it to add them to the StringBuilder and return the resulting string:

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

Time Complexity: O(n) – runtime of the loop is directly proportional to the size of the input string

Ruang Bantu: O (n) - ruang yang dibutuhkan untuk Set tergantung pada ukuran string input; juga, kami menggunakan StringBuilder untuk menyimpan hasilnya

Pertahankan Urutan: LinkedHashSet - Ya, HashSet - Tidak

Dan sekarang, kami telah mencocokkan pendekatan Core Java! Tidaklah terlalu mengejutkan untuk mengetahui bahwa ini sangat mirip dengan apa yang sudah dilakukan oleh perbedaan .

7. Kesimpulan

Pada artikel ini, kami membahas beberapa cara untuk menghapus karakter berulang dari string di Java. Kami juga melihat kompleksitas waktu dan ruang dari masing-masing metode ini.

Seperti biasa, potongan kode dapat ditemukan di GitHub.