使用O(1)额外空间反转单词

一个字符串可能由多个单词组成。C++字符串中的每个单词可以包含字母、数字或特殊符号。字符串被认为是这些字符的存储元素。每个单词由一个空格字符分隔。每个单词也形成一个字符的字符串。在C++中，任何字符串的反向是遵循以下几点的字符串−

• 它是通过从末尾向开头取字符形成的。

• 原始字符串的长度保持不变。

字符在字符串中出现的顺序可以通过交换单词开头和结尾的字符来轻松地颠倒。

常数辅助空间用O(1)表示，这意味着程序在执行过程中不需要额外的空间。

一些说明问题的例子如下：

示例示例

示例1 - str：Abc def

输出：cbA fed

解释：在反转字符串时，字符的情况保持不变。

示例2 - str：嗨spe%32

输出：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是字符串的长度。