8
\$\begingroup\$

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;    
    }
}
\$\endgroup\$
3
  • \$\begingroup\$ I'd skip the spaces in the main loop, instead of having them in the start index calculations. \$\endgroup\$
    – Ron Klein
    Oct 14, 2012 at 5:01
  • 1
    \$\begingroup\$ Your functions word_end_index and word_start_index are effectively rewriting strcspn and strspn. Checkout the standard library! \$\endgroup\$ Oct 15, 2012 at 0:17
  • \$\begingroup\$ Interview in Boulder much? \$\endgroup\$
    – psoft
    Oct 17, 2012 at 14:03

3 Answers 3

5
\$\begingroup\$

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++;

        // skip to the end of the current word
        front = s;
        while(*s != '\0' && !isspace(*s))
            s++;

        // reverse
        back = s-1;
        while (front < back)
            std::swap(*front++, *back--);
    }
}
\$\endgroup\$
4
\$\begingroup\$

Comments on code

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 == ' '))
    

Comments on Algorithm

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(" ");
    }
}
\$\endgroup\$
2
  • \$\begingroup\$ Thanks very much Loki. For the function reverse_string, does it keep the original white space? \$\endgroup\$
    – Fihop
    Oct 17, 2012 at 5:49
  • \$\begingroup\$ No. Space is dropped. \$\endgroup\$ Oct 17, 2012 at 6:45
2
\$\begingroup\$

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==' ';});
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.