Reverse text without reversing the individual words

Given a line of text, reverse the text without reversing the individual words.


 

For example,


Input:  We provide good material for IT Technical Interview preparation

Output: preparation Interview Technical IT for material good provide We

 

 
A simple solution would be to push the individual words starting from the beginning of the text into a stack. Finally, we pop all the words from the stack and store them back into the text in LIFO order. The time complexity of this solution is O(n) and auxiliary space used by the program is O(n) for stack.

 

C++

Download   Run Code

Java

Download   Run Code

Output:

We provide good material for IT Technical Interview preparation

 

 

How can we improve space complexity?

 

The idea is to in-place reverse each individual word present in the input text and finally reverse the whole text to get the desired output. For instance


Input text: preparation Interview Technical IT for material good provide We
 

1. Reverse each individual word –
noitaraperp weivretnI lacinhceT TI rof lairetam doog edivorp eW
 

2. Reverse the whole text –
We provide good material for IT Technical Interview preparation

 
The time complexity of this solution would be O(n) and doesn’t use any auxiliary space. The only problem is that it now does 3 traversals of input text instead of 1.

 

C

Download   Run Code

C++

Download   Run Code

Java

Download   Run Code

Output:

We provide good material for IT Technical Interview preparation

 

 
Exercise: Modify first approach to divide string into tokens by using strtok() in C or stringstream getline() or C++ string class find() function.

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
juest test
Guest

JavaNinja
Guest