Reverse Words in a String - CPP Solution

1. Introduction

This blog post addresses a common string manipulation problem in C++: reversing the order of words in a string. This problem is a typical example that demonstrates handling strings and parsing based on specific delimiters, in this case, spaces.

Problem

Given an input string s, the objective is to reverse the order of the words in it. Each word in s is defined as a sequence of non-space characters, and the words are separated by at least one space. The goal is to return a string where the words appear in reverse order, concatenated by a single space.

2. Solution Steps

1. First, trim leading and trailing spaces from the string.

2. Reverse the entire string.

3. Then, reverse each word in the string.

4. Finally, clean up any extra spaces between words.

3. Code Program

#include <iostream>
#include <algorithm>
using namespace std;

// Function to reverse words in a string
string reverseWords(string s) {
    // Remove leading and trailing spaces
    int start = s.find_first_not_of(" ");
    int end = s.find_last_not_of(" ");
    s = (start == -1) ? "" : s.substr(start, end - start + 1);

    // Reverse the entire string
    reverse(s.begin(), s.end());

    // Reverse each word in the string
    int wordStart = 0;
    for (int i = 0; i <= s.length(); i++) {
        if (s[i] == ' ' || i == s.length()) {
            reverse(s.begin() + wordStart, s.begin() + i);
            wordStart = i + 1;
        }
    }

    // Clean up extra spaces
    string result;
    bool inWord = false;
    for (char c : s) {
        if (c != ' ' || (c == ' ' && inWord)) {
            result += c;
            inWord = (c != ' ');
        }
    }
    return result;
}

int main() {
    string s = "  hello world  ";
    cout << "Reversed: '" << reverseWords(s) << "'" << endl;
    return 0;
}

Output:

Reversed: 'world hello'

Explanation:

1. The input string " hello world " is first trimmed of leading and trailing spaces.

2. The entire string is reversed, resulting in " dlrow olleh".

3. Each word in the reversed string is then reversed, giving "world hello".

4. Extra spaces are removed during the final step, resulting in the clean output "world hello".

5. The function effectively reverses the order of the words and handles extra spaces, leading to the correct output.