Thursday, September 22, 2011

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. 

12 comments:

  1. Isn't it easier to use a stack?

    String str = "hello world I am Andy";
    String temp = "";
    Stack words = new Stack();
    for(int i = 0; i < str.length(); i++) {
    if(str.charAt(i) != ' ') {
    temp += str.charAt(i);
    }
    else {
    words.push(temp);
    temp = "";
    }
    }

    words.push(temp);

    String newStr = "";
    while(!words.isEmpty()) {
    newStr += words.pop();
    if(!words.isEmpty()) {
    newStr += " ";
    }
    }

    System.out.println(newStr);

    ReplyDelete
    Replies
    1. Harry's solution is doing everything in-place (no extra space required).
      If you use a stack, space complexity would be O(n).

      Delete
  2. Yes I think stack can work better.
    We just need to identify individual tokens

    ReplyDelete
  3. String.Join(" ", "I am a student".Split(' ').Reverse().ToArray());

    ReplyDelete
  4. In CPP:
    vectorarr;
    reverse(arr.begin(),arr.end());

    ReplyDelete
  5. @Harry why don't you work from the end, and use another C array to hold the result ?

    ReplyDelete
  6. < Using split function >

    Split the whole sentence word by word and store them in a String array.
    Iterate through the array from end to beginning and add each word to the result.

    < Without using split function >

    Reverse the given string (the whole sentence).
    Reverse each word in the string.

    For explanation and code http://www.algoqueue.com/algoqueue/default/view/7012352/reverse-words-in-a-sentence

    ReplyDelete
  7. Its simply superb.Feeling good to share the link to practice c# interview questions

    @ http://skillgun.com

    ReplyDelete
  8. public String ReverseString(String str){

    str = str.replaceAll("( )+"," "); //make sure only one space between
    String[] parts = str.trim().split(" ");
    String result = "";

    for(String s : parts)
    result=s+" "+result;

    return result;
    }

    ReplyDelete
  9. return " ".join(s.split()[::-1]) works as well.

    ReplyDelete
  10. Salemetsiz Be,


    Grazie! Grazie! Grazie! Your blog is indeed quite interesting around c! I agree with you on lot of points!


    Since yesterday my EC2 instance in Singapore has become

    AWS Tutorial USA to some US customers. Does anyone else have similar problems?


    Please keep providing such valuable information.


    Cheers,

    ReplyDelete
  11. Hey,


    I learnt so much in such little time about No. 07 - Reverse words in a sentence. Even a toddler could become smart reading of your amazing articles.


    I cannot connect to the Windows EC2 instance through remote desktop, only a list of errors I got (see the attached screenshot). I am sure I have started the instance and I have waited long enough. What's the matter?

    AWS Training



    It was cool to see your article pop up in my google search for the process yesterday. Great Guide.
    Keep up the good work!


    Gracias
    Ajeeth

    ReplyDelete