Balikkan perkataan menggunakan O(1) ruang tambahan

Rentetan mungkin terdiri daripada berbilang perkataan. Setiap perkataan dalam rentetan C++ boleh mengandungi huruf, nombor atau simbol khas. Rentetan dianggap sebagai elemen storan untuk aksara ini. Setiap perkataan dipisahkan oleh aksara ruang. Setiap perkataan juga membentuk rentetan satu aksara. Dalam C++, kebalikan mana-mana rentetan ialah rentetan yang mengikuti −

• Ia dibentuk dengan mengambil watak dari akhir ke awal.

• Panjang rentetan asal kekal tidak berubah.

Susunan aksara muncul dalam rentetan boleh diterbalikkan dengan mudah dengan menukar aksara pada permulaan dan akhir perkataan.

Ruang tambahan yang berterusan diwakili oleh O(1), yang bermaksud bahawa program tidak memerlukan ruang tambahan semasa pelaksanaan.

Beberapa contoh untuk menggambarkan masalah adalah seperti berikut:

Contoh Contoh

Contoh 1 - str:Abc def

Output: cbA fed

Penjelasan: Apabila menterbalikkan rentetan, keadaan aksara kekal tidak berubah.

Contoh 2 - str: Hai spe%32

Output: yeH 23%eps

Pernyataan masalah boleh diselesaikan dengan mengekstrak setiap perkataan dan mengekalkan sepasang penunjuk mula dan akhir untuk setiap perkataan dan kemudian menyongsangkannya.

Algoritma

• Langkah 1−Gunakan gelung for untuk mengulangi rentetan input yang disediakan.

• Langkah 2 - Tangkap aksara permulaan perkataan pertama menggunakan pembolehubah st.

• Langkah 3 − Sebaik sahaja ruang pertama ditemui, pembolehubah pertama ditetapkan pada aksara sebelumnya untuk menandakan aksara permulaan dan akhir perkataan.

• Langkah 4 − Menggunakan dua penunjuk dan gelung sementara ini, terbalikkan aksara perkataan. Pada setiap lelaran gelung while, penunjuk digerakkan untuk menghabiskan rentetan.

• Langkah 5 − Nilai dikemas kini untuk mengalihkan penunjuk ke perkataan seterusnya seterusnya dan seterusnya dimulakan semula kepada aksara seterusnya selepas ruang.

• Langkah 6 - Seluruh rentetan diulang dan perkataan yang sepadan diterbalikkan.

Contoh

Snippet kod C++ berikut mengambil rentetan sebagai input dan membalikkan perkataan yang terkandung di dalamnya -

// including the required libraries
#include <bits/stdc++.h>
using namespace std;

//reversing current word of string
void reverseWord(string &st, int s, int e){
   while (s < e) {
      swap(st[s], st[e]);
      s++;
      e--;
   }
}

//reverse the words of a string
string reverseString(string str){
   int len = str.length();

   //initialising the pointer with the first letter of the input string
   int st = 0;
   for (int i = 0; i <= len; i++) {

      //stop the pointer at the first word
      //either a space will be found indicating end of word or the string is finished
      char ch = str[i];
      if (ch == ' ' || i == len) {

         //fetching the last character of the current word of the string
         int lst = i - 1;

         // Reverse the current word
         reverseWord(str, st,lst);

         //since the ith character is string , go to i+1 th character to fetch next word
         st = i + 1;
      }
   }
   return str;
}

//calling the method to reverse words
int main(){

   //input string
   string str = "Reverse words Tutorials Point";
   cout<<"original String:"<<str;

   //reversed string
   string revstr = reverseString(str);
   cout << "\nReversed string : "<< revstr;
   return 0;
}

Output

original String:Reverse words Tutorials Point
Reversed string : esreveR sdrow slairotuT tnioP

Kerumitan ruang

Ruang yang diperlukan oleh kaedah di atas adalah tetap kerana tiada pemulaan baharu bagi sebarang jenis pembolehubah. Tiada storan ruang luaran diperlukan untuk menukar perkataan. Semua pengubahsuaian dibuat dalam pembolehubah storan yang tersedia.

Kesimpulan

String terdiri daripada aksara yang boleh disusun dalam sebarang susunan atau diterbalikkan dengan lelaran mudah. Memandangkan algoritma melakukan satu lelaran untuk keseluruhan julat aksara yang disimpan di dalamnya, jumlah masa yang diperlukan ialah O(n), dengan n ialah panjang rentetan.

Atas ialah kandungan terperinci Balikkan perkataan menggunakan O(1) ruang tambahan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!