Problem Statement

Given an input string, containing upper-case and lower-case letters, digits, and spaces( ' ' ). A word is defined as a sequence of non-space characters. The words in s are separated by at least one space.

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

Examples

Example 1:

Input: s = "welcome to the jungle"
Output: "jungle the to welcome"

Explanation: The words in the input string are "welcome", "to", "the", and "jungle". Reversing the order of these words gives "jungle", "the", "to", and "welcome". The output string should have exactly one space between each word.

Example 2:

Input: s = " amazing coding skills "
Output: "skills coding amazing"

Explanation: The input string has leading and trailing spaces, as well as multiple spaces between the words "amazing", "coding", and "skills". After trimming the leading and trailing spaces and reducing the multiple spaces between words to a single space, the words are "amazing", "coding", and "skills". Reversing the order of these words gives "skills", "coding", and "amazing". The output string should not have any leading or trailing spaces and should have exactly one space between each word.

Different Approaches

1️⃣ Brute Force Approach

Intuition:

A brute force way to solve the problem will be to extract every word from the given string. Once all the words are extracted, the resulting string can be formed by adding all the words in the reverse order keeping a space in between.

Approach:

1. First, the string is scanned to extract words, which are sequences of non-space characters.
2. These words are stored in a list while ignoring extra spaces.
3. Once all the words are collected, they are concatenated in reverse order to form the result.
4. The words are joined with a single space between them, ensuring no trailing or leading spaces in the final output.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to reverse every word in the given string
    string reverseWords(string s) {
        int n = s.length(); // Length of string
        
        // List to store the words present in string
        vector<string> words;
        
        // Pointers to mark the start and end of a word
        int start, end;
        
        int i = 0;
        while(i < n) {
            
            // Finding the first character of a word (if any)
            while(i < n && s[i] == ' ') i++;
            
            // If no word is found, break 
            if(i >= n) break;
            
            start = i; // Storing the index of first character of word
            
            // Finding the last character of the word
            while(i < n && s[i] != ' ') i++;
            
            end = i-1; // Storing the index of last character of word
            
            // Add the found word to the list of words
            string wordFound = s.substr(start, end-start+1);
            words.push_back(wordFound);
        }
        
        string ans = "";
        
        // Adding all the words to result in the reverse order 
        for(int i = words.size() - 1; i >= 0; i--) {
            ans += words[i];
            
            // Adding spaces in between words
            if(i != 0) ans.push_back(' ');
        }
        
        return ans; // Return the stored result
    } 
};

int main(){
    string s =  " amazing coding skills ";
    
    // Creating an instance of Solution class
    Solution sol; 
    
    // Function call to reverse every word in the given string
    string ans = sol.reverseWords(s);
    
    // Output
    cout << "Input string: " << s << endl;
    cout << "After reversing every word: " << ans << endl;
}

Complexity Analysis:

• Time Complexity: O(n) (where n is the length of the input string)
  • The input string is scanned once to extract words, taking O(n) time, where n is the length of the input string.
  • Each word is stored in a list and then concatenated in reverse order, which also takes O(n).
• Space Complexity: O(n)
  • The words list stores each extracted word, requiring O(k) space, where k is the total number of characters in all words (essentially O(n)).
  • The result string requires O(n) space as well.