No. 07 - Reverse words in a sentence

Problem: Reverse the order of words in a sentence, but keep words themselves unchanged. Words in a sentence are divided by blanks. For instance, the reversed output should be “student. a am I” when the input is “I am a student”.

Analysis: This is a very popular interview question of many companies. It can be solved with two steps: Firstly we reverse all characters in a sentence. If all characters in sentence “I am a student.” are reversed, it becomes “.tneduts a ma I”. Not only the order of words is reversed, but also the order of characters inside each word is reversed. Secondly, we reverse characters in every word. We can get “student. a am I” from the example input string with these two steps.

The key of our solution is to implement a function to reverse a string, which is shown as the Reverse function below:

void Reverse(char *pBegin, char *pEnd)

{

    if(pBegin == NULL || pEnd == NULL)

        return;

    while(pBegin < pEnd)

    {

        char temp = *pBegin;

        *pBegin = *pEnd;

        *pEnd = temp;

        pBegin ++, pEnd --;

    }

}

Now we can reverse the whole sentence and each word based on this Reverse function with the following code:

char* ReverseSentence(char *pData)

{

    if(pData == NULL)

        return NULL;

    char *pBegin = pData;

    char *pEnd = pData;

    while(*pEnd != '\0')

        pEnd ++;

    pEnd--;

    // Reverse the whole sentence

    Reverse(pBegin, pEnd);

    // Reverse every word in the sentence

    pBegin = pEnd = pData;

    while(*pBegin != '\0')

    {

        if(*pBegin == ' ')

        {

            pBegin ++;

            pEnd ++;

        }

        else if(*pEnd == ' ' || *pEnd == '\0')

        {

            Reverse(pBegin, --pEnd);

            pBegin = ++pEnd;

        }

        else

        {

            pEnd ++;

        }

    }

    return pData;

}

Since words are separated by blanks, we can get the beginning position and ending position of each word by scanning blanks. In the second phrase to reverse each word in the sample code above, the pointer pBegin points to the first character of a word, and pEnd points to the last character.

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages,  please add a referenced to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact the author via zhedahht@gmail.com . Thanks.