Compact, readable, efficient C++ algorithm to reverse the words of a string IN-PLACE

Question

So I'm trying to come up with a good C++ solution to the prompt

"Reverse words in a string (words are separated by one or more spaces). Now do it in-place. By far the most popular string question!"

and what I have now is a monstrosity:

void reverse_words ( std::string & S )
{
/* 
    Programming interview question: "Reverse words in a string (words are separated by one or more spaces). Now do it in-place. By far the most popular string question!"
    http://maxnoy.com/interviews.html 
*/
    if (S.empty()) return;
    std::string::iterator ita = S.begin() , itb = S.end() - 1;
    while (ita != itb) 
    {
      if (*ita != ' ')
      {
         std::string sa; // string to hold the current leftmost sequence of non-whitespace characters
         std::string::iterator tempa = ita; // iterator to the beginning of sa within S
         while (ita != ' ' && ita != itb) sa.push_back(*ita++); // fill sa
         while (*itb == ' ' && itb != ita) --itb; // move itb back to the first non-whitespace character preceding it
         std::string sb; // string to hold the current rightmost sequence of non-whitespace characters
         std::string::iterator tempb = itb; // iterator to the end of sb within S
         while (*itb != ' ' && itb != ita) sb.push_back(*itb--); // fill sb
         S.replace(tempa, ita-tempa, sb); // replace the current leftmost string with the current rightmost one
         S.replace(tempb, itb-tempb, sa); // and vice-versa
       }
      else
      {
         ++ita; 
      }
    }   
}

I think I have the right idea (find the first string, swap it with the last, find the next string after the first, swap it with the one before the last, etc.), but I need some better tools to make this happen. How can I exploit the standard library to solve this problem?

The usual way to do this is to reverse the entire string. Then reverse each word. — dting, Apr 20 '15 at 04:23

score 3 · Answer 1 · answered Apr 20 '15 at 04:59

This is pretty simple if you use the following approach:

Reverse the whole string.
Reverse each word individually.

This algorithm is already O(n), you just run through the whole string once and then again to find an reverse each word.

Now, in order to make this a bit more efficient, look at the algorithm to reverse a sequence, which reads one from the front and back and stores each at the other's position. Now, whenever you store a space, you just terminated a word, so just reverse the word right now. The reason that is more efficient is that the cache containing that word is still hot on the CPU. The difficulty here is getting this right in cornercases. You have to consider the middle word, multiple consecutive spaces and spaces at either end of the string.

Lingxi · Answer 2 · 2015-04-20T05:59:22.483

I guess this is it. Simple, efficient, and clear. Note that std::basic_string::find... returns npos when pos >= str.size().

void ReverseWords(std::string& msg) {
    std::string::size_type pos_a = 0, pos_b = -1;
    while ((pos_a = msg.find_first_not_of(' ', pos_b + 1)) != msg.npos) {
        pos_b = std::min(msg.find(' ', pos_a + 1), msg.size());
        std::reverse(msg.begin() + pos_a, msg.begin() + pos_b);
    }
    std::reverse(msg.begin(), msg.end());
}

Compact, readable, efficient C++ algorithm to reverse the words of a string IN-PLACE

2 Answers2