Reverse words in a string

Reverse words in a string

A string can contain many words which are separated by space. We need to reverse words in a string. For example if string is “this is test string” , output should be “string test is this”

Reverse words in a string

What do i get if reverse the whole string first? In above example, we get “gnirts tset si siht”. Notice that first word in reverse string is exact reverse of first word of the output string. Similarly second word is exact reverse of the second word of the output string.

So we can just reverse individual words in the string and get the output like string. Hence the algorithm involves two simple steps:
1. Reverse the whole string first.
2. Reverse individual words of the output string given in step 1.
Same algorithm can be used when we want to rotate an array with a given index as pivot.

Reverse words of a string implementation

#include <stdio.h>
#include <stdlib.h>

/* This function reverses the whole string */
void reverse(char s[]){
        int i=0, j;
        int end =  strlen(s);

        for(i=0, j=end-1; i<j; i++, j--){
                char temp = s[i];
                s[i] = s[j];
                s[j] = temp;
        }

}
/* This function reverses a given word, we need to 
provide stat and end of the word */
void reverse_word(char * start, char * end){
        while(start < end){
                char temp = *start;
                *start++ = *end;
                *end-- = temp;
        }
}

void reverse_words(char *string){
        char * source = string;
        char *begin = string;

        if(string == NULL) return;

        /* Step 1 : Reverse the whole string */
        reverse(string);

        /* Now reverse individual words in reversed string */
        while(*source != '\0'){
                if(*(source +1) == ' ') {
                        reverse_word(begin, source);
                        begin =  source + 2;
                        source++;
                        
                }
             /*Case when it is last word of string */
                else if(*(source + 1) == '\0'){
                        reverse_word(begin, source);
                }
                source++;
        }       
}

/* driver program to run above code */
#define MAX_LENGTH 100
int main(){
    char string[MAX_LENGTH] = "This is a test string";
    reverse_words(string);
    return 0;
}

Test cases

1. A Normal string with multiple words
s = "This is test string"

2. A string with only one word
s ="string"

3. An empty string
s =""

4. A NULL pointer is passed
s =  NULL

Rotate an array with a given index as pivot

void reverseArray(int a[], int start, int end){

    while(start < end){     
        int temp =  a[start];
        a[start] = a[end];
        a[end] = temp;
        start++;
        end--;
    }
}

void rotateArray(int a[], int pivot, int len){
        int i;
        /*Reverse the whole array */
        reverseArray(a, 0, len);

        /* Reverse from 0 to pivot and pivot to end */
        reverseArray(a,0, pivot);
        reverseArray(a,pivot+1,len);
}

int main(){
   int a[] = {1,2,3,4,5,6,7};
   int size = sizeof(a)/sizeof(a[0]);

   rotateArray(a, 3, size);

   return 0
}

Complexity of method to reverse words in a string or rotate an array is O(N) without using any extra space. 

Please share if there is something missing or wrong. If you are interested in contributing to website please contact us.