In this article, we will learn how to write a program in C++ language to reverse a given string (a sentence) and will also walk through the algorithm step by step.
Reversing the words of a given string is quite simple if we follow the following three steps:
-
We first reverse each word present in the string one by one.
-
Once all the words present in the given string are reversed then we reverse the complete sentence.
-
While iterating over any given string, we can find out the words present in it by collecting characters together till an empty space is encountered and then doing the same over and over again till the end of line character, which is \0.
Quick Think:
For proceeding to the algorithm of the above problem statement we need to think for the following points:
- We need to pass the pointer to the string variable to avoid errors in our code and to store the given pointers to the first and the last letter of the string which will be used for the reversing purpose and finding the empty spaces between the two words.
- Every time we encounter an empty space we will call the reverse function and reverse the current word and then move forward towards the other word.
- And if we encounter the last letter of the last word in the given sentence we will simply reverse the word.
Algorithm:
Algorithm for the above implementation will be as follows:
Create a function which will take the string’s address to the first letter and then follow the following steps to design the algorithm:-
Step1: Define the two variable pointers which will store the address to the first letter of the string or the sentence.
Step2: Now, while loop is executed with the argument as the address of the first letter of the string or the sentence and increment the address of the variable which holds the address of the last or initially we can say the first letter of the word in the given string, so that everytime we increment it’s address we can easily check by the condition that the pointer to the address of the letter has reached the end of the word or the string or the sentence and as the last letter of the word of the given string reaches the loop ultimately breaks.
Step3: Now, the condition is enforced to check the pointer pointing to the address of the last letter of the word used in reversing each word, if it reaches the end of the string then, the function to reverse the current last word is called and the word is reversed else go to step 4.
Step4: Another, condition is enforced to check the space between the two words in the current string or the sentence, if the space is found then the function is called and the current word is reversed and the starting pointer to the first letter of the next word is set to the next of the terminating pointer to the last word.
Step5: After each and every word of the given string or the sentence is reversed then, it’s the time to reverse the entire string or the sentence and then calling the same reverse function we will reverse the entire string and hence, we obtain the required output.
Implementation Of The Above Algorithm:
#include <bits/stdc++.h>
using namespace std;
void reverse(char *begin, char *end)
{
char temp;
while (begin < end)
{
temp = *begin;
*begin++ = *end;
*end-- = temp;
}
}
/*Function to reverse the word along with the complete string. */
void wordstringreverse(char *str)
{
/*Begin pointer, pointing to the address of the first letter. */
char *word_begin = str;
/*End pointer, pointing to the address of the first letter. */
char *word_end = str;
while (*word_end)
{
// increment the pointer
*word_end++;
/*Checks whether the sentence ends or not. */
if (*word_end == '\0')
reverse(word_begin, word_end - 1);
/*Checks whether a word has ended or not. */
else if (*word_end == ' ')
{
reverse(word_begin, word_end - 1);
word_begin = word_end + 1;
}
}
/*Reverses the complete sentence. */
reverse(str, word_end - 1);
}
/*Driver function to test above functions */
int main()
{
char str[] = "i like to sleep";
wordstringreverse(str);
cout << str;
getchar();
return 0;
}
The Running Time Complexity Of The Above Algorithm is O(n).
The Output Of The Above Algorithm Test Case is: sleep to like i.
Explanation Of The Above Algorithm:
The above algorithm can be understood very easily as, let us take an example of the string mentioned above, now we will follow the following steps to reach to the final output:-
- The example we will take is shown in the figure above.
- Now, according to our algorithm we can see that the first word gets skipped as it is of only one letter, hence we move on to the next word and till we don’t find the space between two words we will keep traversing the loop and now, we reach to the letter ‘e’ of the word ‘like’ and our word_begin pointer points to the address of the first letter ‘l’ and hence reverse function is called and the word gets reversed as shown in the above diagram.
- Now the word_begin points to the first letter of the word ‘to’ and again similarly till we don’t find the space between two words we will keep traversing the loop and now, we reach to the letter ‘o’ of the word ‘to’ and our word_begin pointer points to the address of the first letter ‘t’ and hence reverse function is called and the word gets reversed as shown in the above diagram.
- again, similarly following the previous step for the word ‘sleep’ and we get the word as shown in the diagram above.
- Now combining the entire sentence we have as shown in the above diagram.
- And finally reversing the entire sentence we have the following final output as shown in the diagram above.
