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\$
  • \$\begingroup\$ I'd skip the spaces in the main loop, instead of having them in the start index calculations. \$\endgroup\$ – Ron Klein Oct 14 '12 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\$ – William Morris Oct 15 '12 at 0:17
  • \$\begingroup\$ Interview in Boulder much? \$\endgroup\$ – psoft Oct 17 '12 at 14:03
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--);
    }
}
| improve this answer | |
\$\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(" ");
    }
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks very much Loki. For the function reverse_string, does it keep the original white space? \$\endgroup\$ – Fihop Oct 17 '12 at 5:49
  • \$\begingroup\$ No. Space is dropped. \$\endgroup\$ – Martin York Oct 17 '12 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==' ';});
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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