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
- Fungsi Swap: Kita menggunakan fungsi pembantu
swap
untuk menukar karakter dalam array. - Fungsi Reverse String: Fungsi ini membalik karakter dari string menggunakan fungsi swap.
- 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!