Internship at OpenGenus

Get this book -> Problems on Array: For Interviews and Competitive Programming

This problem is similar to many standard competetive problems with strings and words, but what makes this a bit tricky is the question itself because as soon as we read it we feel it is familiar like just reversing the letters of the string by printing them inreverse etc, but what read it once again here in this problem we need to reverse each word in the string i.e in place reverse, order of the words will be the same but they are just reversed.

Example:

              Input: hello world Output : olleh dlrow   Input : Open Genus Output : nepO suneG  //works irrespective of capital or small letters

Solution Approach

So, basically we know how to reverse a word i.e by reversing the order or swaping the front letters with back letters. Now the problem is detecting each word in the string and treating them seperately, this can be done easily by detecting spaces in between each word and then reversing each word and adding it to the string so that all words remain in the same position without moving.

Steps

  1. Get the string
  2. Iterate through each character in the string
  3. Whenever we find a space '_' in between pass the string from the beginning till this space to a reverse function
  4. In the reverse function we simply swap the first and last letters from both sides thus reversing the word
  5. Now, back to iteration of the string, we start from the end of previous word
  6. Repeat above steps till we reach the end of the string
  7. Print the reversed string

Explanation

  • We start with a simple while loop that iterates till we reach the end of the string
  • We have start and end locations of the string, we iterate till we reach a '_' single space i.e end now pass this start and end to a reverese function
  • The reverse function uses simple swap from start and end i.e both sides start++ and end-- till start < end till both pointers meet we keep swapping characters of both sides, thus reversing the words
  • Now back to iteration the previous end will become new start and we iterate till we find the next space and then keep passing all words to the reverse funciton
  • Finally we reach the end of the string and all the words are already reversed, print the output

Pseudocode

  1. Start
  2. Initialize start and end variables
  3. Start iterating through all characters of the string till we reach the end
  4. 'start' and 'end' both start from 0 position, however we keep incrementing the 'end' till we reach a single '_' space
  5. Once we reach a space means that we have the start and end location of the word, now we pass this start and end to a reverse funciton
  6. Inn the reverse function we swap the charcters from front and end till the middle i.e all characters are now swapped i.e the word is reversed
  7. Now the new start value is the end of previous value +1 for space, start=end+1 and the next end will be the position of the next space
  8. This continues till we reach the end of the string and all the words will be reversed in their own places by the end
  9. Print the reversed string
  10. End

Program in C

              #include<stdio.h> void reverse_string(char str[], int start, int end) {     char temp;     while(start<end)     {         temp=str[start];         str[start]=str[end];         str[end]=temp;         start++;         end--;     } } int main() {     char str[]="reverse this string word by word";     int start, end;     end=0;     start=0;     while(str[end])     {         for(end=start;str[end]&&str[end]!=' ';end++);         reverse_string(str, start, end-1);         start=end+1;     }         printf("%s ",str);     return 0; }  OUTPUT: esrever siht gnirts drow yb drow

Like I said already the best part of this is that it works for all kinds of words i.e even capital or small letters without any conversiona as we are swapping them in places.

Example Step by Step Explaination

Start

              Input String: Hello World
  • Initialize the variables
  • start=0, end=0
  • We iterate through all characters in while loop till we reach the end of the string while(str[end])
  • Now we have the inner for loop, end=start=0; this stops if the string ends else if there is a single character space str[end]='_' and increment end++
  • str[0] = H (end++)
  • str[1] = e (end++)
  • str[2] = l (end++)
  • str[3] = l (end++)
  • str[4] = o (end++)
  • str[5] == '_'
  • Now we found the first space stop the loop and pass the start and end of the string locations to the reverse function
  • start = 0 str[0] = H
  • end = 4 str[4] = o
  • In the reverse function we perform standard swapping
  • temp= str[0] (temp = H)
  • str[0]=str[4] (str[0] = o)
  • str[4]=temp (str[4]=H)
  • start++ and end-- as long as start < end
  • So this is how other letters are swapped
  • o ->e l l<- H
  • o l ->l<- e H
  • Now start == end condition fails and we exit the reverse function
  • Back to iteration, since we finished reversing a word now we should start iterating for the next word but don't forget to skip the space between them.
  • That's why our new start=end+1 (1 to skip the space)
  • Nw str[start] = str[6] = W
  • Ad end++ until a new space or the string ends
  • A there are no new words we halt at the end of the string
  • str[6] = W (end++)
  • str[7] = o (end++)
  • str[8] = r (end++)
  • str[9] = l (end++)
  • str[10] = d (end++)
  • We pass start and end to reverse function
  • str[start] = str[6] = W
  • str[end] = str[10] = d
  • Start swapping
  • ->W o r l d<-
  • d ->o r l<- W
  • d l ->r<- o W
  • start==end condition fails(start<end)
  • Exit function
  • Exit iteration loop [reached end of string]
  • Print the reversed string
  • olleH dlroW

End

Thoughts and different approaches

Here we deal with string reversing problem but we peform inplace revresing i.e without adding more characters we perform simple swapping however we can't just directly swap all characters of the string as it would reverse not only the whole string but the order of the words is changed, by using single space '_' as the condition to seperate words and then we perform swapping seperately on each character of the word.

With this article at OpenGenus, you must have the complete knowledge of solving this problem of Reverse a String word by word in C, Enjoy.