Secara Efisien Membalik Urutan Kata dalam Array Karakter

Membalik urutan kata dalam array karakter adalah masalah klasik yang menguji pemahaman Anda tentang algoritma dan manipulasi string. Baik Anda sedang mempersiapkan wawancara atau hanya ingin mengasah keterampilan pemrograman Anda, menguasai tantangan ini cukup menguntungkan. Dalam artikel ini, kita akan menjelajahi masalah ini secara detail dan membahas solusi yang efisien dalam C/C++.

Masalah

Diberikan sebuah array karakter yang membentuk sebuah kalimat, tujuan kita adalah membalik urutan kata tanpa mengubah huruf individual dalam kata-kata tersebut. Sebagai contoh, jika Anda memasukkan:

"this is a string"

Output yang diharapkan adalah:

'string a is this'

Tantangan ini menetapkan bahwa operasi ini harus dicapai dalam waktu O(N) dan ruang O(1), yang berarti Anda tidak dapat menggunakan fungsi seperti split() atau struktur data tambahan seperti tumpukan yang memanipulasi ruang tambahan.

Menganalisis Masalah

Kompleksitas Waktu

Persyaratan untuk kompleksitas waktu O(N) berarti algoritma harus melakukan pemrosesan linear terhadap data. Oleh karena itu, kita harus menghindari loop bersarang yang dapat meningkatkan kompleksitas waktu.

Kompleksitas Ruang

Untuk kompleksitas ruang O(1), kita tidak dapat menggunakan struktur data tambahan untuk penyimpanan. Ini berarti operasi harus dilakukan langsung dalam array input.

Solusi

Mari kita pecah solusi ini menjadi langkah-langkah. Kita akan memanfaatkan pendekatan dua kali untuk menyelesaikan masalah ini secara efisien.

Langkah 1: Membalik Seluruh String

Langkah pertama adalah membalik seluruh array. Ini mengubah string asli menjadi string di mana semua karakter dibalik. Untuk contoh kita "this is a string" setelah dibalik:

"gnirts a si siht"

Langkah 2: Membalik Setiap Kata

Sekarang setelah kita membalik seluruh string, kita perlu membalik setiap kata individual agar berada dalam urutan yang benar. Berikut adalah cara kita dapat mengimplementasikan langkah-langkah ini dalam C/C++:

void swap(char* str, int i, int j) {
    char t = str[i];
    str[i] = str[j];
    str[j] = t;
}

void reverse_string(char* str, int length) {
    for(int i = 0; i < length / 2; i++) {
        swap(str, i, length - i - 1);
    }
}

void reverse_words(char* str) {
    int l = strlen(str);
    // Membalik seluruh string
    reverse_string(str, strlen(str));
    int p = 0;
 
    // Mencari batas kata dan membalik kata demi kata
    for(int i = 0; i < l; i++) {
        if(str[i] == ' ') {
            reverse_string(&str[p], i - p);  // Membalik kata yang teridentifikasi
            p = i + 1;
        }
    }
    // Akhirnya membalik kata terakhir.
    reverse_string(&str[p], l - p);
}

Penjelasan Kode

  1. Fungsi Swap: Kita menggunakan fungsi pembantu swap untuk menukar karakter dalam array.
  2. Fungsi Reverse String: Fungsi ini membalik karakter dari string menggunakan fungsi swap.
  3. Fungsi Reverse Words: Fungsi inti pertama membalik seluruh array karakter dan kemudian mengiterasi melalui array untuk membalik kata individual yang diidentifikasi oleh spasi. Kata terakhir ditangani setelah loop selesai.

Analisis Kompleksitas

Pembalikan melalui array dua kali menjadikan kompleksitas waktu O(N):

  • Pass pertama: O(N) untuk membalik seluruh string.
  • Pass kedua: O(N) untuk membalik setiap kata.

Dengan demikian, kompleksitas waktu akhir tetap O(N). Kompleksitas ruang adalah O(1) karena tidak ada ruang tambahan yang digunakan selain variabel untuk iterasi.

Kesimpulan

Membalik urutan kata dalam array karakter secara efisien memerlukan kombinasi manipulasi string dan pemahaman tentang akses terindeks. Algoritma yang disajikan di sini menunjukkan pendekatan yang jelas yang memenuhi persyaratan waktu O(N) dan ruang O(1) sambil menggunakan C/C++. Latihlah solusi ini, dan Anda akan menemukan bahwa ini adalah tambahan yang sangat baik untuk alat pemrograman Anda!