# Write a program to reverse words in a string

From :  http://stackoverflow.com/questions/47402/given-an-array-of-characters-which-form-a-sentence-of-words-give-an-efficient-al


Python Case:
>>> a = "These pretzels are making me thirsty"
>>> " ".join(a.split()[::-1])
'thirsty me making are pretzels These'

C/C++ Case:

void swap(char* str, int i, int j){

  char t = str[i];

  str[i] = str[j];

  str[j] = t;

}

void reverse_string(char* str, int length){

  for(int i=0; i<length/2; i++){

      swap(str, i, length-i-1);

  }

}

void reverse_words(char* str){

  int l = strlen(str);

  //Reverse string

  reverse_string(str,strlen(str));

  int p=0;

  //Find word boundaries and reverse word by word

  for(int i=0; i<l; i++){

      if(str[i] == ' '){

          reverse_string(&str[p], i-p);

          p=i+1;

      }

  }

  //Finally reverse the last word.

  reverse_string(&str[p], l-p);

}

This should be O(n) in time and O(1) in space.

Edit: Cleaned it up a bit.

The first pass over the string is obviously O(n/2) = O(n). The second pass is O(n + combined length of all words / 2) = O(n + n/2) = O(n), which makes this an O(n) algorithm.