Reverse words using O(1) extra space

A string may consist of multiple words. Each word in a C string can contain letters, numbers, or special symbols. Strings are considered storage elements for these characters. Each word is separated by a space character. Each word also forms a string of one character. In C, the reverse of any string is a string that follows −

• It is formed by taking characters from the end to the beginning.

• The length of the original string remains unchanged.

The order in which the

characters appear in a string can be easily reversed by swapping the characters at the beginning and end of the word.

Constant auxiliary space is represented by O(1), which means that the program does not require additional space during execution.

Some examples to illustrate the problem are as follows:

ExampleExample

Example 1 - str:Abc def

Output: cbA fed

Explanation: When reversing a string, the condition of the characters remains unchanged.

Example 2 - str: Hi spe2

Output: yeH 23%eps

The problem statement can be solved by extracting each word and maintaining a pair of start and end pointers for each word and then inverting it.

algorithm

• Step 1−Use a for loop to traverse the provided input string.

• Step 2 - Use variable st to capture the starting character of the first word.

• Step 3 − Once the first space is encountered, the lst variable is fixed on the previous character to mark the starting and ending characters of the word.

• Step 4 − Using these two pointers and a while loop, reverse the characters of the word. On each iteration of the while loop, the pointer is moved to exhaust the string.

• 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.

• Step 6 - The entire string is iterated and the corresponding words are reversed.

Example

The following C code snippet takes a string as input and reverses the words contained in it -

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

Space complexity

The space required by the above method is constant because there is no new initialization of any type of variables. No external space storage is required to swap words. All modifications are made in available storage variables.

in conclusion

Strings are composed of characters that can be arranged in any order or reversed by simple iteration. Since the algorithm performs a single iteration for the entire range of characters stored in it, the total time required is O(n), where n is the length of the string.

The above is the detailed content of Reverse words using O(1) extra space. For more information, please follow other related articles on the PHP Chinese website!