Description: We have to reverse the ordering of words in a sentence while  maintaining the same order of characters within a word.

 
If video does not load, Click here
 
Example:
Input:
 
I love to code
Output:

code to love I

Algorithm:

Step 1:

Reverse all characters in the entire string.

This step would align the words in their required positions.

Eg:

“I love to code”

“edoc ot evol I” ->after step 1

Till  now, the words have been aligned in the required positions.

 However, the alignment of characters in the words is in reverse order.

 

Step 2:

Reverse the order of characters within each word.

Now, the sequence within each word is correct.

In our example,

“edoc ot evol I” after step 1

“code to love I” after step 2

Time Complexity:

O(n), where n is the length of the string.

 

Implementation in C:

 

/* UTILITY FUNCTIONS */
void reverse(char *begin, char *end)
{
  char temp;
  while (begin < end)
  {
    temp = *begin;
    *begin++ = *end;
    *end-- = temp;
  }
}
 
/* Function to reverse order of words */
void reverseWords(char *s)
{
    char *wordbeg = NULL;
    char *temp = s; /* temp is for word boundary */
 
    /*STEP 1 */
    while( *temp )
    {
        /*This condition is to make sure that the string start with valid character (not space) only*/
        if (( wordbeg == NULL ) && (*temp != ' ') )
        {
            wordbeg=temp;
        }
        if(wordbeg && ((*(temp+1) == ' ') || (*(temp+1) == '\0')))
        {
            reverse(wordbeg, temp);
            wordbeg = NULL;
        }
        temp++;
    }
 
    /*STEP 2 */
    reverse(s, temp-1);
}
Go to top