Monday, 11 April 2011

Reverse only the words in string

 

Introduction

   Another popular interview question is, reverse the words in the string. We have seen how to do string reverse, simply by swapping the last character with first. But when it comes to reversing just words in the sentence, we should be careful as we also need to do this in-place. When you do in-place reverse of just words, you might need to move the letter further in the string which is unnecessary and confusing.

Approach

  Easy approach is to reverse the whole string using string reverse and then reverse each word one-by-one. I wanted to solve a Google code jam practice problem as well parallel

http://code.google.com/codejam/contest/dashboard?c=351101#s=p1

The above problem requires reversing the words in the strings given as input.

Example:

Input: this is  a test

Output: test a is this

How would do this?

Just string reverse the whole string and then reverse each word one-by-one

Intermediate: tset a si siht

Reverse each word: test a is this

Code

char* str_rev_words(char* str)
{
    char* result = str;
    while(*str != '\0') {
        char* tstr = str;
        char* istr = tstr; // string start
        while(1) {
            if(*(tstr+1) == ' ' || *(tstr+1) == '\0') break;
            tstr++;            
        }
        char* estr = tstr; // string end
        while(!(istr >= estr))
        {
            char tmp = *istr;
            *istr = *estr;
            *estr = tmp;
            istr++;
            estr--;
        }
        if(*(tstr+1) == '\0')
            str = tstr+1;
        else
            str = tstr+2;
    }
    return result;
}
 
#include <fstream>
 
using namespace std;
 
void main()
{
    char line[1000];
    ifstream myfile ("C:\\Works\\cppassignments\\algorithms\\B-large-practice.in");
    ofstream outfile ("C:\\Works\\cppassignments\\algorithms\\result.txt");
    myfile.getline(line, 1000);
    int num_of_cases = atoi(line);
    for(int i=1; i<=num_of_cases; i++)
    {
        myfile.getline(line, 1000);
        // doProblem
        str_rev(line);
        outfile<<"Case #"<<i<<": "<<str_rev_words(line)<<endl;
    }
    outfile.close();
    myfile.close();
}

Important points:

  • You must note that not just ‘ ‘ is the separator for the word. When you reach the last word, even ‘\0’ will become the separator.
  • BUG FIX: When you are reversing the string using swapping last and first, sometimes, first might go beyond than last so, it should be >= condition.