Reverse words

The second problem proposed in the Google Code Jam Qualification Round Africa 2010, asks to revert the words in a number of strings given in input. It is a simpler request than the first one in the round, but still there are a couple of points worth of spending some thinking.

The core of the question is defining a function like this (if you solve it in C++):

std::string revert(const std::string& input)

I have written a few test cases to drive the development, like this one:

TEST(TestRevert, Case1)
{
    std::string input = "this is a test";
    std::string reverted = "test a is this";

    std::string output = revert(input);

    EXPECT_EQ(output, reverted);
}

Then I spent some time asking myself how to actually implement the function. My first idea has been to use an input string stream to extract the words from the string, put them in a container, and then, via an output string stream, generate the output string.

It is not the best solution that one could came out with, in term of efficiency, but it has the advantage of being clean, easy to write, and event kind of fun.

Let's see it:

std::string revert(const std::string& input)
{
    std::vector<std::string> words;
    std::istringstream iss(input);
    std::string item;
    while(iss >> item)
        words.push_back(item); // 1

    if(words.empty())
        return ""; // 2

    std::ostringstream oss; // 3
    std::for_each(words.rbegin(), words.rend() - 1, [&oss](const std::string& cur) // 4
    {
        oss << cur << ' ';
    });
    oss << words[0]; // 5

    return oss.str(); // 6
}

1. I loop on the input string stream until there is something in it. By default, all blank characters are discarded by the put-to operator, so I just have to push back any word I get in the buffer container.
2. What if nothing was in the input string? I simply return an empty one.
3. Otherwise, I want to loop backward on all the collected words, putting in the output stream any single word followed by a blank. With the noticeable exception of the last one, that has no following blank.
In C++ you could do that using the for_each() STL algorithm, delimiting the range with the reverse iterators rbegin() - pointing to the last element in the collection - and the decremented rend() - pointing to the first one (remember that the "end" element in a iteration is the first out of the selection).
4. As functional to be executed on each element in the range, I defined a lambda function (I love them). If your compiler do not support them, I am sorry to say you have to rearrange the code, probably using a functor, or a plain for loop. In the capture clause I specified the above defined output string stream, passed by reference, so that we can use it inside the lambda body.
5. The first word in the collection is the last element sent to the output stream.
6. Finally, I extract the string from the stream, and I return it.

I like this code, still it has a couple of issues. Most importantly, it could be too expensive. If we have to process lots and lots of input lines, creating and using all those string streams could be easily become a pain.

This second version is stream-free, as this means faster. You could even get rid of STL strings, but you will pay this extra performance gain with an extra code readability loss. For our requirements, I assumed this is enough:

std::string revert(const std::string& input)
{
    std::vector<std::string> words;

    size_t beg = 0; // 1
    size_t end = 0;
    do {
        end = input.find(' ', beg); // 2
        std::string word(input.begin() + beg, (end == std::string::npos ? input.end() : input.begin() + end)); // 3
        words.push_back(word);
        beg = end + 1; // 4
    } while(end != std::string::npos); // 5

    std::string output;
    output.reserve(input.length()); // 6
    std::for_each(words.rbegin(), words.rend() - 1, [&output](const std::string& cur) // 7
    {
        output += cur;
        output += ' ';
    });
    output += words[0];

    return output;
}

1. I use a couple of variables to keep track of the beginning and end of a single world in the input.
2. Search the end of the word starting on beg (first iteration, beg is zero). If there is no blank after beg, find() return string::npos to signal it.
3. Let's build a word, starting from begin() + beg, and ending to end(), if no blank is found, or to the actual blank position.
4. The new beg value is the next one after the current end, meaning, the first character after the last used blank. Actually, it doesn't much sense to assign to beg string::npos + 1, how it happens in case no blank has been found, but it is harmless (see next point for the reason).
5. We loop until end is string::npos, that means, we have already scanned the complete input line.
6. Let's generate the output string. I know its size (same as input), so I (possibly) save some time specifying it.
7. The output construction loop is almost the same as in the previous version. What changes is that I work on the actual STL string, and not on the string stream.