# reverse every word in a string(should handle space)

Examples:

``````char test1[] = "               ";
char test2[] = "   hello  z";
char test3[] = "hello world   ";
char test4[] = "x y z ";
``````

Results:

``````"               "
"   olleh  z"
"olleh dlrow   "
"x y z "
``````

The problem:

Reverse every world in a string, ignore the spaces.

The following is my code. The basic idea is to scan the string, when finding a word, then reverse it. The complexity of the algorithm is O(n), where n is the length of the string.

Could anyone help me verify it? Is there any better solution?

``````void reverse_word(char* s, char* e)
{
while(s < e)
{
char tmp = *s;
*s = *e;
*e = tmp;
++s;
--e;
}
}

char* word_start_index(char* p)
{
while((*p != '\0') && (*p == ' '))
{
++p;
}

if(*p == '\0')
return NULL;
else
return p;
}

char* word_end_index(char* p)
{
while((*p != '\0') && (*p != ' '))
{
++p;
}

return p-1;
}

void reverse_string(char* s)
{
char* s_w = NULL;
char* e_w = NULL;
char* runner = s;

while(*runner != '\0')
{
char* cur_word_s = word_start_index(runner);
if(cur_word_s == NULL)
break;
char* cur_word_e = word_end_index(cur_word_s);
reverse_word(cur_word_s, cur_word_e);
runner = cur_word_e+1;
}
}
``````
-
I'd skip the spaces in the main loop, instead of having them in the start index calculations. –  Ron Klein Oct 14 '12 at 5:01
Your functions `word_end_index` and `word_start_index` are effectively rewriting `strcspn` and `strspn`. Checkout the standard library! –  William Morris Oct 15 '12 at 0:17
Interview in Boulder much? –  psoft Oct 17 '12 at 14:03

If using C++ is an option for you (which your tags suggest), then you might consider using `std::swap` for swapping the characters. You might also want to use `isspace` to check for whitespace other than `' '`.

You could also write it all in a single function:

``````void reverse_every_word(char* s)
{
char* front;
char* back;
while(*s != '\0')
{
// handle whitespace
while(*s != '\0' && isspace(*s))
s++;

front = s;
while(*s != '\0' && !isspace(*s))
s++;

// reverse
back = s-1;
while (front < back)
std::swap(*front++, *back--);
}
}
``````
-

In C++ code you do not want to be messing with C-Strings. All that memory management makes the code hard to maintain and is difficult to get correct. prefer to use std::string which does all the hard work and lets you concentrate on the algorithm.

``````void reverse_word(char* s, char* e)
``````

There are already algorithms for reversing stuff `std::reverse()` and swapping the two values `std::swap()` so there is no need to implement either.

``````    while(s < e)
{
char tmp = *s;
*s = *e;
*e = tmp;
++s;
--e;
}
``````

Space `' '` is not the only white space character. Rather than explicitly testing for a space you should use the standard function for testing if a character is white space `std::is_space()`

``````    while((*p != '\0') && (*p == ' '))
``````

There is already a std::reverse() algorithm.
Using this would reduce the complexity of your code to just finding the beginning and end of each word. Since `operator>>` does this automatically it makes the code very trivial:

``````void reverse_string(std::string& paragraph)
{
std::stringstream pStream(paragraph);
std::string       word;

paragraph.clear();
while(pStream >> word)
{
std::reverse(word.begin(), word.end());
paragraph.append(word);
paragraph.append(" ");
}
}
``````
-
Thanks very much Loki. For the function reverse_string, does it keep the original white space? –  FihopZz Oct 17 '12 at 5:49
No. Space is dropped. –  Loki Astari Oct 17 '12 at 6:45

Having C++11, we could do,

``````template<class InputIterator, class UnaryPredicate>
void reverseSeparate(InputIterator first, InputIterator last, UnaryPredicate pred)
{
first = std::find_if_not(first,last,pred);
while(first!=last){
InputIterator t = std::find_if(first,last,pred);
std::reverse(first,t);
first = std::find_if_not(t,last,pred);
}
}
``````

using this, we can (among other things) reverse every word in a string.

``````std::string s = "hi   hello world ";
reverseSeparate(s.begin(),s.end(), [](char c){return c==' ';});
``````
-