使用O(1)額外空間反轉單字

一個字串可能由多個單字組成。 C 字串中的每個單字可以包含字母、數字或特殊符號。字串被認為是這些字元的儲存元素。每個單字由一個空格字元分隔。每個單字也形成一個字元的字串。在C 中，任何字串的反向是遵循以下幾點的字串−

• 它是透過從末尾向開頭取字元形成的。

• 原始字串的長度保持不變。

字元在字串中出現的順序可以透過交換單字開頭和結尾的字元來輕鬆地顛倒。

常數輔助空間以O(1)表示，這表示程式在執行過程中不需要額外的空間。

一些說明問題的例子如下：

範例範例

範例1 - str：Abc def

#輸出：cbA fed

解釋：在反轉字串時，字元的情況保持不變。

範例2 - str：嗨spe2

輸出：yeH 23%eps

#問題陳述可以透過提取每個單字並為每個單字維護一對開始和結束指針，然後進行反轉來解決。

演算法

• 第一步−使用for迴圈次歷提供的輸入字串。

• 第二步 - 使用變數st捕捉第一個單字的起始字元。

• 步驟 3 − 一旦遇到第一個空格，lst變數就會固定在前一個字元上，以標記單字的起始和結束字元。

• 步驟 4 − 使用這兩個指標和一個 while 循環，將該單字的字元反轉。在每次 while 迴圈的迭代中，指標會被移動以窮盡字串。

• Step 5 − The values are updated to shift the pointers to the next subsequent word and so on. st is reinitialised to the next character after space.

• 第6步 - 整個字串被迭代，對應的單字被反轉。

範例

以下的C 程式碼片段以一個字串作為輸入，並反轉其中包含的單字 -

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

輸出

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

空間複雜度

上述方法所需的空間是恆定的，因為沒有對任何類型的變數進行新的初始化。不需要外部空間儲存來交換單字。所有的修改都是在可用的儲存變數中進行的。

結論

字串由字元組成，可以按任意順序排列或透過簡單的迭代反轉。由於演算法對儲存在其中的字元的整個範圍執行單次迭代，所需的總時間為O(n)，其中n是字串的長度。

以上是使用O(1)額外空間反轉單字的詳細內容。更多資訊請關注PHP中文網其他相關文章！