Reverse Words in C++

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by one space for simplicity.

Return a string of the words in reverse order concatenated by a single space.

Example:

Input:  input = "sky is blue"

Output:  "blue is sky"

Understanding the Problem

The core challenge of this problem is to reverse the order of words in a given string. This is a common problem in text processing and has applications in various fields such as natural language processing and data formatting. A potential pitfall is to mistakenly reverse the characters within the words instead of reversing the order of the words themselves.

Approach

To solve this problem, we can follow these steps:

Split the input string into words.
Reverse the order of the words.
Join the words back into a single string with spaces in between.

Let's discuss a naive solution and then move on to an optimized approach.

Naive Solution

A naive solution would involve manually iterating through the string to identify words, storing them in a list, and then reversing the list. This approach, while straightforward, can be inefficient due to the manual handling of string operations.

Optimized Solution

An optimized solution leverages built-in string manipulation functions to split, reverse, and join the words efficiently. This reduces the complexity and makes the code cleaner and more maintainable.

Algorithm

Here is a step-by-step breakdown of the optimized algorithm:

Use a string stream to split the input string into words.
Store the words in a vector.
Reverse the vector of words.
Join the reversed words into a single string with spaces in between.

Code Implementation

#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>

std::string reverseWords(const std::string &s) {
    std::istringstream iss(s);
    std::vector<std::string> words;
    std::string word;
    
    // Split the string into words
    while (iss >> word) {
        words.push_back(word);
    }
    
    // Reverse the order of words
    std::reverse(words.begin(), words.end());
    
    // Join the words back into a single string
    std::ostringstream oss;
    for (size_t i = 0; i < words.size(); ++i) {
        if (i != 0) {
            oss << " ";
        }
        oss << words[i];
    }
    
    return oss.str();
}

int main() {
    std::string input = "sky is blue";
    std::string output = reverseWords(input);
    std::cout << output << std::endl; // Output: "blue is sky"
    return 0;
}

Complexity Analysis

The time complexity of this solution is O(n), where n is the length of the input string. This is because we are iterating through the string to split it into words and then iterating through the list of words to reverse and join them. The space complexity is also O(n) due to the storage of words in a vector.

Edge Cases

Consider the following edge cases:

Empty string: The output should be an empty string.
String with multiple spaces: The solution should handle multiple spaces correctly by treating them as word separators.

Examples:

Input:  input = ""
Output:  ""

Input:  input = "  hello  world  "
Output:  "world hello"

Testing

To test the solution comprehensively, consider the following test cases:

Simple cases with a few words.
Edge cases with empty strings and strings with multiple spaces.
Long strings to test performance.

Using a testing framework like Google Test can help automate and manage these tests effectively.

Thinking and Problem-Solving Tips

When approaching such problems, it's important to:

Break down the problem into smaller, manageable parts.
Consider edge cases and how to handle them.
Optimize the solution by leveraging built-in functions and data structures.

Practicing similar problems and studying algorithms can significantly improve problem-solving skills.

Conclusion

In this blog post, we discussed how to reverse the words in a string using C++. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for improving coding skills and preparing for technical interviews.

Additional Resources

For further reading and practice, consider the following resources:

Reverse Words in a String - C++ Solution and Time Complexity Analysis