Reversing words of a sentence in C++

Explanation of 4 different methods that aren’t the only way to do it.

So reversing words of a given sentence is a popular question in fresher interviews and I am guilty of not being able to do this one during my very first interview. As I chose C++ as the object-oriented language I was to interview in, I was asked to implement the above in C++. To be honest, I thought they asked me to reverse the given string, like for the string, “CPP is amazing”, the answer would be “gnizama si PPC”. On explaining my approach, the interviewer figured out that I didn’t pay attention to the question and used the above example and told that the right answer was “amazing is CPP”. So in case, you don’t get my explanation for the problem and aren’t interested in reaching out to me, I hope that you learned a small lesson from my experience. Listen carefully to what question is being asked in an interview and if you don’t get it the first time, ask them to repeat.

Video Explanation of all the below approaches

The First Approach:-

So on understanding this question correctly, I suppose you may have an approach in mind. Mine was to store the words in an array and then get them printed in the reverse order. The space characters would separate the words and once you count the number of words, you could create a string array of the required size. Simple, right? Well, let's look at the code doing just that.

The Algorithm goes like:-

1. Get the needed string from the user. I have used the getline function as it accepts a string with space characters. (lines 14–17)
2. Then we parse through the given sentence and count the no. of words based on the space characters, such that a word is counted only when a space character is encountered after it. I am assuming that there will be no space character after the last word, so I have incremented the counter once after the loop is finished. In case that a space character is the last character in the sentence, we should ignore it. (lines 19–24)
3. Now that we know the no. of words, we can create an array of strings and store the words individually in each index of the array. The memory is assigned at runtime depending on the length of the sentence given by the user. I have used the stringstream class, which is a buffer that stores strings in a one after the other fashion. By creating a stringstream object ‘ss’ and initializing it with the given sentence, the constructor stores the words sequentially by removing the space characters. (lines 26–28)
4. The separated words are stored in the earlier array of strings that we created, from the stringstream object ‘ss’. (lines 30–32)
5. Finally, the stored words are printed in the reverse order. We start from the last index position to the first and enter space characters in between. (lines 34–36)

Well, we got the desired output, but to be honest, I saw that there was much scope for improvement and made the following changes.

An Improved Version:-

It is best to avoid assigning memory at run-time wherever possible. Although the code written in first_approach.cpp will run, its line no. 21 will be shown as a problem in the Visual Studio Code IDE. Thus we will be replacing the string array with a new string. Also, instead of storing the words in the array and then accessing them in the reverse order, we can store the words in the string itself in the reverse order and just print it. Let’s look at the code implementing this.

The code is the same as first_approach.cpp till line no. 24. The changes in the improved version are:-

1. We are going to store the result directly in a ‘revSentence’ string instead of using a string array and thus declare it. We also separated and stored the words of the sentence in the buffer as done earlier in the first_approach.cpp. (lines 26–27)
2. Using a for loop based on the number of the words in the sentence, we get each of the word stored in the stringstream object ‘ss’ one by one in the exact order as the given sentence. Using a temporary string variable word, we get the word from ‘ss’ and insert them at the beginning of the ‘revSentence’ String. This is done using the insert() function of the String library, where the first parameter specifies the position of the string to be entered and the second parameter is the string itself. We add spaces between the words except for the last word. If this is not done, the resultant string would start with a space character and we don’t want that. (lines 29–35)
3. Lastly, we can print the new ‘revSentence’ string. (line 37)

Let us suppose that you are not happy with using stringstream and want to see how we could separate the words from the sentence and also want to do the whole thing in a single loop to reduce the time complexity, I have got another algorithm for you. Mind you, this one is my favourite.

My Favourite Approach:-

So in this method of reversing words of a sentence, I am going to be using only one loop and am also going to show how we can obtain the separate words from the sentence. This approach uses 2 string library functions, insert() and substr(). Words are taken from the sentence and added to a new ‘revSentence’ variable simultaneously. Let’s see how to do this.

The steps of this approach are:-

1. Take the input sentence from the user
2. Create a ‘revSentence’ variable to store the reversed words sentence and Initialize ‘start’ and ‘length’ variables to 0. The start variable points to the starting position of a word and the length variable indicates the length of the word.
3. Go through the sentence letter by letter till we encounter a space character or the last character of the sentence, using a for loop.
4. On encountering a space character, the length variable is updated to (i-start) and the substr() function is used to get the word substring from the sentence. The substr() function has 2 parameters, where the first parameter must be the index from where the substring is being obtained and the second parameter is the length of this substring. So for the first word ‘CPP’, the space character is encountered at i=3, so the length will be i-start = 3–0 = 3. The word ‘CPP’ will be copied into the string variable ‘word’. The start variable will be updated to i+1 = 4 to indicate where the next word begins from. In the start of the ‘revSentence’ string, ‘CPP’ will be added first and then a space character is added before it. These above steps will take place till no more space characters are encountered.
5. On seeing the last character, the length variable is updated to (i-start+1) as the value of index ‘i’ is being taken at the last character of the word instead of the value after it. No space is added at the beginning as it is not the desired characteristic of our final string.
6. Now, we output the result ‘revSentence’ string.

This is the best possible method I could come up with by optimizing my original idea on how to tackle this problem. I welcome any suggestions that further optimise this code. I do have one last trick to solve this problem and trust me, it's magical.

A Magic Trick:-

When I first saw this method on the net, I was dumbfounded on how someone can think of a solution in this manner. Being able to solve this problem, in this approach, at the first attempt. according to me, is very unlikely. I believe that one would really need to be someone that thinks out of the box to solve this problem in such a manner or should spend some quality time analysing the various inputs and outputs to observe this pattern or else they should be extremely lucky.

Recall “gnizama si PPC” from the start of this post. Well, the magic trick has something to do with this phrase. Take a moment to observe and see if you can figure it out.

All you need to do is reverse the individual words and you will get the required answer, that is “amazing is CPP”. So let’s take a look at a final code using this trick.

In this method, all the operations are performed on the same sentence variable itself. The steps followed can be explained as:-

1. Define a function that reverses a given string from a start to an end point. I have used the reference operator ‘&’ so that reversing operation on the string done in the function is reflected in the given ‘sentence’ variable itself. A char variable ‘temp’ is used to performing the swapping operation till the centre of the start and end index positions is reached.
2. Take the input sentence from the user
3. Call the reverseString() function on the whole sentence to swap all the characters in it.
4. While parsing through the sentence, call the reverseString() function on each word including the last word.
5. In the end, we can print the reversed sentence.

wael9823/ReversedWords

Mohammed Wael - Hyderabad, Telangana, India | Professional Profile | LinkedIn

So, that’s all folks. I hope this was helpful and that you were able to discover multiple ways to solve this common but slightly tricky interview question. If there are any other interview questions you would like me to do or if you have any queries or insights, do let me know in the comments. I look forward to hearing from you all. Wishing you a good day ahead.