Membalikkan string di Java: belajar membalikkan string dengan berbagai cara

Mungkinkah menjadi programmer yang baik tanpa mengetahui algoritma? Sangat, sangat kontroversial. Ya, Anda dapat mencari pekerjaan di perusahaan outsourcing kami, karena selama wawancara mereka kebanyakan menanyakan pertanyaan tentang teknologi. Tetapi apakah Anda akan menjadi spesialis yang baik jika keputusan Anda penuh dengan kruk? Jika Anda ingin pindah ke perusahaan asing yang lebih serius, Anda akan menghadapi wawancara yang terutama berfokus pada algoritma. Dengan satu atau lain cara, ada baiknya mengadopsi algoritma yang paling dasar, karena algoritma adalah teman programmer . Hari ini kita akan membahas salah satu topik ini dan mendiskusikan cara membalikkan string. Semuanya sederhana di sini. Membalikkan string berarti membuat string mundur. Misalnya: JavaRush forever ->reverof hsuRavaJ Jadi, bagaimana Anda bisa membalikkan string di Java?

1. Pembuat String/StringBuffer

Cara paling umum dan sederhana adalah dengan menggunakan StringBuilder/StringBuffer :

public static String reverseString(String str) {
  return new StringBuilder(str).reverse().toString();
}

Solusi terbaik = paling sederhana. Ketika ditanya bagaimana cara membalikkan string di Java, ini adalah hal pertama yang harus terlintas dalam pikiran. Tapi kita sudah membicarakan algoritma sebelumnya, bukan? Mari kita lihat solusi yang tidak biasa.

2. Solusi susunan

public static String reverseString(String str) {
  char[] array = str.toCharArray();
  String result = "";
  for (int i = array.length - 1; i >= 0; i--) {
     result = result + array[i];
  }
  return result;
}

Kami mengubah string kami menjadi array menggunakan metode toCharArray . Mari kita jalankan perulangan for melalui array ini dari ujungnya, sambil menambahkan karakter ke string yang dihasilkan.

3. Solusi dengan charAt

public static String reverseString(String str) {
  String result = "";
  for (int i = 0; i < str.length(); i++) {
     result = str.charAt(i) + result;
  }
  return result;
}

Dalam hal ini, kita bahkan tidak perlu membagi string menjadi sebuah array, karena kita mengekstrak setiap karakter menggunakan metode kelas String - charAt (perulangan for, sekali lagi, adalah kebalikannya, yang memungkinkan kita mengambil karakter secara berurutan ke belakang).

4. Solusi dengan Stack

Belum ada seorang pun yang menggunakan kelas Stack untuk waktu yang lama, dan kelas ini dianggap ketinggalan jaman, namun demikian, sebagai referensi, akan berguna untuk melihat solusi yang menggunakannya:

public static String reverseString(String str) {
  Stack<Character> stack = new Stack<>();
  String result = "";
  for (Character character : str.toCharArray()) {
     stack.add(character);
  }
  while (!stack.isEmpty()) {
     result = result + stack.pop();
  }
  return result;
}

Di sini sekali lagi kita menggunakan toCharArray untuk membagi string menjadi sebuah array dan meletakkan semuanya di Stack kita dengan tipe generik Character . Selanjutnya, kita mulai mengambil elemen dari atas tumpukan. Karena sifat tumpukan sebagai struktur LIFO - L ast I n First Out ( masuk pertama, keluar terakhir), elemen akan diambil mundur dan hasilnya akan disimpan di baris yang dihasilkan.

5. Solusi dengan rekursi

Hampir setiap masalah algoritma dapat diselesaikan dengan menggunakan rekursi. Dan di sini kita juga tidak bisa hidup tanpanya. Atau bahkan tanpa mereka. Lagi pula, hari ini kita akan mempertimbangkan tidak hanya satu metode penyelesaian rekursi, tetapi beberapa.

• metode satu

  public static String reverseString(String str) {
    String rightStr;
    String leftStr;
    int length = str.length();
  
    if (length <= 1) {
       return str;
    }
  
    leftStr = str.substring(0, length / 2);
    rightStr = str.substring(length / 2, length);
  
    return reverseString(rightStr) + reverseString(leftStr);
  }

  Kami menggunakan variabel rightStr dan leftStr untuk membagi string masuk menjadi dua bagian yang sama. Selanjutnya, dengan menggunakan pemisahan ini, kita membagi string menjadi bagian terkecil yang dapat dibagi (1 karakter). Setelah itu, rekursi mulai runtuh, mengembalikan karakter dalam urutan yang berlawanan (karakter yang berada di kanan ditempatkan di kiri; karakter yang berada di kiri ditempatkan di kanan)

  Kita tidak boleh lupa bahwa setiap rekursi merupakan pemanggilan beberapa metode, dan sebagai hasilnya, menghabiskan banyak sumber daya. Nah, jika kita berbicara tentang rekursi dengan kondisi keluar yang tidak dapat dicapai, maka ini adalah jalan menuju tak terhingga dan ke StackOverflowError.

• metode dua

  Di sini kita memerlukan argumen tambahan dalam metode - index.

  Saat metode ini dijalankan, diberikan panjang string -1:

  String str = "JavaRush forever";
  System.out.println(reverseString(str, str.length()-1));

  Dan caranya sendiri:

  public static String reverseString(String str, int index) {
    if(index == 0){
       return str.charAt(0) + "";
    }
  
    char letter = str.charAt(index);
    return letter + reverseString(str, index-1);
  }

  Indeks kita berfungsi sebagai indikator elemen baris mana yang akan kita gunakan sekarang (dan kita akan menggunakan elemen dari akhir).

  Oleh karena itu, kami menetapkan kondisi keluar ketika indeks mencapai elemen pertama.

Kami menambahkan nilai yang diperoleh menggunakan indeks huruf dengan hasil eksekusi metode sebelumnya dan mengembalikan hasilnya.

• metode tiga

  public static String reverseString(String str) {
    if (str.length() <= 1) {
       return str;
    }
    return reverseString(str.substring(1)) + str.charAt(0);
  }

  Metode ini pada dasarnya adalah metode rekursif yang paling sederhana. Dan seperti yang kita ingat, sederhana = terbaik.

  Selama setiap proses, kami menentukan string yang sama, tetapi tanpa elemen pertama. Ketika kondisi keluar tercapai (ketika kita memiliki satu karakter tersisa), rekursi mulai diciutkan, dan karakter sebelumnya yang tidak digunakan akan ditambahkan ke setiap hasil berikutnya.

6. Menggunakan XOR

XOR adalah operasi bitwise yang logis. Dalam kasus dua variabel, hasil suatu operasi bernilai benar jika dan hanya jika salah satu argumennya benar dan argumen lainnya salah. Anda dapat membaca lebih lanjut tentang operasi bitwise di artikel ini . Solusi selanjutnya akan bergantung pada fakta bahwa:

(A XOR B) XOR B = A
(A XOR B) XOR A = B

Seperti apa tampilan metodenya:

public static String reverseString(String str) {
  char[] arr = str.toCharArray();
  int low = 0;
  int high = arr.length - 1;
  String result = "";
  while (low < high) {
     arr[low] = (char) (arr[low] ^ arr[high]);
     arr[high] = (char) (arr[low] ^ arr[high]);
     arr[low] = (char) (arr[low] ^ arr[high]);
     low++;
     high--;
  }
  for (int i = 0; i < arr.length; i++) {
     result = result + arr[i];
  }
  return result;
}

Mari kita cari tahu apa yang terjadi di sini. Kami membuat array dari string yang masuk. Kami membuat dua variabel, low dan high , yang menyimpan indeks untuk melintasi array. Oleh karena itu, yang satu akan berpindah dari awal ke akhir - kita beri nilai 0, yang kedua - dari akhir ke awal, kita atur arr.length - 1 . Kita memasuki loop yang akan diputar selama indeks high lebih besar dari low . Di sinilah hal menyenangkan mulai terjadi - penggunaan OR eksklusif. Mari kita lihat x dan y sebagai contoh . Misalkan arr[tinggi] = 'x'; Kode binernya adalah 1 1 1 1 0 0 0 Saat ini arr[high] = 'n'; Kode biner - 1 1 0 1 1 1 0 Apa yang akan kita miliki dalam operasi XOR dalam satu lingkaran:

1. arr[rendah] = (char) (arr[rendah] ^ arr[tinggi]);

   
   arr[low] = 1 1 0 1 1 1 0
   arr[high] =1 1 1 1 0 0 0
   arr[low] = 0 0 1 0 1 1 0

2. arr[tinggi] = (arang) (arr[rendah] ^ arr[tinggi]);

   
   arr[low] =  0 0 1 0 1 1 0
   arr[high] = 1 1 1 1 0 0 0
   arr[high] = 1 1 0 1 1 1 0

3. arr[rendah] = (char) (arr[rendah] ^ arr[tinggi]);

   
   arr[low] =  0 0 1 0 1 1 0
   arr[high] = 1 1 0 1 1 1 0
   arr[low] =  1 1 1 1 0 0 0

Hasilnya, berkat operasi ini, kami menukar nilai dari dua sel array. arr[high] adalah jumlah elemen dari akhir array sebanyak arr[low] dari awal. Oleh karena itu, kami cukup menukar elemen dengan indeks ini. Misalnya pada eksekusi pertama pada kalimat “JavaRush forever” J dan r akan ditukar, pada eksekusi kedua - a dan e , dst. Jika kita memiliki jumlah karakter ganjil, maka ketika kita mencapai elemen yang ada di tengah, kita akan dikeluarkan dari loop (yaitu tidak perlu mengubah elemen tengah). Jika genap, kita akan diusir setelah memproses semua elemen. Nah, setelah itu kita masuk ke loop biasa dan membuat string dari elemen array.