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.

 
C++ implementation –
 

Download   Run Code

Output:

We provide good material for IT Technical Interview preparation

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n) for stack.
 


 

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

 
C++ implementation –
 

Download   Run Code

Output:

We provide good material for IT Technical Interview preparation

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1). The only problem is that it now does 3 traversals of input text instead of 1.
 

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

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

Notify of
avatar
wpDiscuz