Monday 11 April 2011

Reverse only the words in string



   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.


  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

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


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


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;
        char* estr = tstr; // string end
        while(!(istr >= estr))
            char tmp = *istr;
            *istr = *estr;
            *estr = tmp;
        if(*(tstr+1) == '\0')
            str = tstr+1;
            str = tstr+2;
    return result;
#include <fstream>
using namespace std;
void main()
    char line[1000];
    ifstream myfile ("C:\\Works\\cppassignments\\algorithms\\");
    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
        outfile<<"Case #"<<i<<": "<<str_rev_words(line)<<endl;

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.


No comments:

Post a Comment