Periksa apakah Two Strings adalah Anagram di Java

1. Ikhtisar

Menurut Wikipedia, anagram adalah kata atau frasa yang dibentuk dengan mengatur ulang huruf dari kata atau frase yang berbeda.

Kita dapat menggeneralisasi ini dalam pemrosesan string dengan mengatakan bahwa anagram dari sebuah string adalah string lain dengan kuantitas yang sama persis dari setiap karakter di dalamnya, dalam urutan apa pun .

Dalam tutorial ini, kita akan melihat mendeteksi seluruh anagram string di mana kuantitas setiap karakter harus sama, termasuk karakter non-alfa seperti spasi dan digit. Misalnya, “! Rendah garam!” dan “owls-lat !!” akan dianggap sebagai anagram karena mengandung karakter yang persis sama.

2. Solusi

Mari bandingkan beberapa solusi yang dapat menentukan apakah dua string adalah anagram. Setiap solusi akan memeriksa di awal apakah kedua string memiliki jumlah karakter yang sama. Ini adalah cara cepat untuk keluar lebih awal karena input dengan panjang berbeda tidak dapat berupa anagram .

Untuk setiap solusi yang mungkin, mari kita lihat kompleksitas implementasi untuk kita sebagai pengembang. Kami juga akan melihat kompleksitas waktu untuk CPU, menggunakan notasi O besar.

3. Periksa dengan Menyortir

Kita dapat mengatur ulang karakter dari setiap string dengan mengurutkan karakternya, yang akan menghasilkan dua array karakter yang dinormalisasi.

Jika dua string adalah anagram, bentuk normalnya harus sama.

Di Java, pertama-tama kita dapat mengubah dua string menjadi array char [] . Kemudian kita dapat mengurutkan dua larik ini dan memeriksa kesetaraan:

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

Solusi ini mudah dipahami dan diterapkan. Akan tetapi, keseluruhan running time dari algoritma ini adalah O (n log n) karena pengurutan array dari n karakter membutuhkan waktu O (n log n) .

Agar algoritme berfungsi, algoritme harus membuat salinan dari kedua string input sebagai larik karakter, menggunakan sedikit memori tambahan.

4. Periksa dengan Menghitung

Strategi alternatif adalah menghitung jumlah kemunculan setiap karakter dalam masukan kami. Jika histogram ini sama antara input, maka stringnya adalah anagram.

Untuk menghemat sedikit memori, mari buat hanya satu histogram. Kami akan menambah jumlah untuk setiap karakter di string pertama, dan mengurangi jumlah untuk setiap karakter di string kedua. Jika kedua string tersebut adalah anagram, maka hasilnya adalah semuanya seimbang menjadi 0.

Histogram memerlukan tabel hitungan ukuran tetap dengan ukuran yang ditentukan oleh ukuran kumpulan karakter. Misalnya, jika kita hanya menggunakan satu byte untuk menyimpan setiap karakter, maka kita dapat menggunakan ukuran array penghitungan 256 untuk menghitung kemunculan setiap karakter:

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

Solusi ini lebih cepat dengan kompleksitas waktu O (n) . Namun, dibutuhkan ruang ekstra untuk larik penghitungan. Pada 256 bilangan bulat, untuk ASCII itu tidak terlalu buruk.

Namun, jika kita perlu meningkatkan CHARACTER_RANGE untuk mendukung himpunan karakter multi-byte seperti UTF-8, ini akan menjadi sangat haus memori. Oleh karena itu, ini hanya benar-benar praktis jika jumlah karakter yang mungkin berada dalam kisaran kecil.

Dari sudut pandang pengembangan, solusi ini berisi lebih banyak kode untuk dipelihara dan mengurangi penggunaan fungsi perpustakaan Java.

5. Periksa dengan MultiSet

Kita dapat menyederhanakan proses penghitungan dan perbandingan dengan menggunakan MultiSet . MultiSet adalah koleksi yang mendukung kesetaraan independen-order dengan elemen duplikat. Misalnya, multiset {a, a, b} dan {a, b, a} sama.

Untuk menggunakan Multiset , pertama-tama kita perlu menambahkan dependensi Guava ke file pom.xml proyek kita :

 com.google.guava guava 28.1-jre  

Kami akan mengubah setiap string input kami menjadi MultiSet karakter. Kemudian kami akan memeriksa apakah mereka sama:

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

Algoritma ini memecahkan masalah dalam waktu O (n) tanpa harus mendeklarasikan array hitung besar.

Ini mirip dengan solusi penghitungan sebelumnya. Namun, daripada menggunakan tabel ukuran tetap untuk menghitung, kami memanfaatkan kelas MutlitSet untuk mensimulasikan tabel berukuran variabel, dengan hitungan untuk setiap karakter.

Kode untuk solusi ini lebih memanfaatkan kapabilitas pustaka tingkat tinggi daripada solusi penghitungan kami.

6. Anagram berbasis huruf

Contoh-contoh tersebut sejauh ini tidak sepenuhnya mengacu pada definisi linguistik dari anagram. Ini karena mereka menganggap karakter tanda baca sebagai bagian dari anagram, dan peka huruf besar / kecil.

Mari sesuaikan algoritme untuk mengaktifkan anagram berbasis huruf. Mari kita pertimbangkan hanya penataan ulang huruf peka huruf besar / kecil, terlepas dari karakter lain seperti spasi dan tanda baca. Misalnya, "Titik desimal" dan "Saya titik di tempat". akan menjadi anagram satu sama lain.

Untuk mengatasi masalah ini, pertama-tama kita dapat memproses dua string input untuk menyaring karakter yang tidak diinginkan dan mengubah huruf menjadi huruf kecil. Kemudian kita dapat menggunakan salah satu solusi di atas (katakanlah, solusi MultiSet ) untuk memeriksa anagram pada string yang diproses:

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

Pendekatan ini dapat menjadi cara umum untuk menyelesaikan semua varian masalah anagram. Misalnya jika kita juga ingin memasukkan angka, kita tinggal menyesuaikan filter preprocessing.

7. Kesimpulan

Pada artikel ini, kami melihat tiga algoritma untuk memeriksa apakah string yang diberikan adalah anagram dari karakter lain, karakter untuk karakter. Untuk setiap solusi, kami membahas trade-off antara kecepatan, keterbacaan, dan ukuran memori yang diperlukan.

Kami juga melihat bagaimana mengadaptasi algoritma untuk memeriksa anagram dalam pengertian linguistik yang lebih tradisional. Kami mencapai ini dengan memproses masukan menjadi huruf kecil.

Seperti biasa, kode sumber artikel tersedia di GitHub.