Level-wise traversal of a binary tree
June 12, 2012
Print ancestors of a node in a Binary Tree Node
June 13, 2012

Reversing words in a String

Given a String, reverse the string but do not reverse the words. For example, if

 Input : "MCN Professionals is now Ritambhara"
 Output: "Ritambhara now is Professionals MCN"

Your function should not take more that O(n) time in the worst case.

Solution:

The solution to this problem is very simple, It uses the reverse algorithms. You can easily write a reverse function to reverse the entire string. Its logic will be like below:

For i = START to MID
    swap(str[i] , str (n-i))

Once, we have this reverse function then the algorithm to reverse the array word-wise will be as below:

Algorithm:

Step-1: Reverse entire string
Step-2: Reverse individual words in the string

For example:

Input:

"MCN Professionals is now Ritambhara"

Reverse the entire string

"arahbmatiR won si slanoisseforP NCM"

Now reverse individual words in the string

"Ritambhara now is MCN Professionals"

Code:

Let u first write the reverse function, which can reverse the part of a string (it take start & end position in a string)

    void reverse(char *str, int startpos, int endpos)
    {
        int i = startpos;
        int len = startpos + (endpos-startpos)/2;
        for (; i<len+1; i++)
        {
            char temp = str[i];
            str[i] = str[endpos-i + startpos];
            str[endpos-i + startpos] = temp;
        }
    }

Main function to reverse the string word-wise

    void reverseWords(char* str)
    {
        int len = strlen(str)-1;
        // reversing the Entire string.
        reverse(str, 0, len);
        int startpos = 0;
        int i = 0;
        while(i<=len)
        {
            i++;
            // If character is a white space or end of the string is reached
            if(str[i] == ' ' || str[i] == '\t' ||
                str[i] == '\n' || str[i] == '\0')
            {
                reverse(str, startpos, i-1);
                // updating i to point to the next non-space character
                while( (str[i] == ' ' || str[i] == '\t' ||
                        str[i] == '\n') && (str[i] != '\0') )
                    i++;
                startpos = i ;
            }
        }
    }

2 Comments

  1. Ali says:

    Your code is not working. Please test it, correct and repost again.
    Also, when posting code it is a good idea to post complete code from #include down to return 0, to avoid confusion.
    Thanks anyway for your trial, maybe you need a little more effort.

    • Neil says:

      In these kind of cases its always good to post only relevant part of the code. Also the algorithm and approach is already given in this article. “Spoon feeding” is not always necessary so one should not crib about syntax of this sample code.

Leave a Reply to Barryrek Cancel reply

Your email address will not be published. Required fields are marked *