Reverse Words in a String

DevSniper
Published : 21 July 2024

160 Views

Given an input string str reverse the order of the words of str.

Note : The input string str may include leading or trailing spaces as well as multiple spaces between words. The resulting string should have each word separated by exactly one space without any additional spaces.

Example 1 :-

Reverse Words in a String

Output : String a in Words Reverse

Example 2 :-

I    love       programming

Output : programming love I

Constraints :

1 <= str.length <= 10^4
String str contains English letters (upper-case and lower-case), digits and spaces.
There is at least one word in string str

Approach 1 : Using Stack

Idea behind this approach is to store string words into a stack so all words will be in stack in reverse order. Then pop elements of the stack one by one and add them to our answer variable. It's important to include a space between each word during this process.

C++

Java

Python

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

string ReverseWords(string str)
{
    stack<string> stk;
    string temp="";
    for(int i=0; i<str.size(); i++) {
        if(str[i]==' ' &amp;&amp; temp.empty()) {
            continue;
        } else if(str[i]==' ') {
            stk.push(temp);
            temp="";
        } else {
            temp+=str[i];
        }
    }
    if (!temp.empty()) {
        stk.push(temp);
    }
    string ans="";
    while(!stk.empty()) {
        ans+=stk.top()+" ";
        stk.pop();
    }
    return ans;
}
int main()
{
    string str="  Reverse Words in a   String  ";
    cout<<ReverseWords(str)<<endl;
}

String a in Words Reverse

Time Complexity

We are iterating over array so Time Complexity will be => O(N)

Space Complexity

We are storing element in the Stack so Space Complexity will be => O(N)

Approach 2 : Using Array

Instead of using a stack as shown in the above approach. We can use an array. We store words in the array and during the creation of the answer variable. We iterate the array in reverse order.

C++

Java

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

string ReverseWords(string str)
{
    vector<string> arr;
    string temp="";
    for(int i=0; i<str.size(); i++) {
        if(str[i]==' ' &amp;&amp; temp.empty()) {
            continue;
        } else if(str[i]==' ') {
            arr.push_back(temp);
            temp="";
        } else {
            temp+=str[i];
        }
    }
    if (!temp.empty()) {
        arr.push_back(temp);
    }
    string ans="";
    for(int i=arr.size()-1;i>=0;i--)
    {
        ans+=arr[i]+" ";
    }
    return ans;
}
int main()
{
    string str="  Reverse Words in a   String  ";
    cout<<ReverseWords(str)<<endl;
}

String a in Words Reverse

Time Complexity

We are iterating over array so Time Complexity will be => O(N)

Space Complexity

We are storing element in the Array so Space Complexity will be => O(N)

Approach 3 : Optimized Solution

Instead of using extra memory to store words. we can optimize the process by iterating through the string in reverse order and simultaneously creating answer variable. This approach avoids the need for storing words in a separate data structure.

Steps :

Create an answer and temp variable and initialize with empty string.
Iterate over array in reverse order.
If string character is space then check for temp variable if temp variable is empty continue loop for next character otherwise add temp in answer variable with space and reset temp variable to empty.
If string character is not a space add that character in temp variable as a prefix of temp variable.
After completing the loop, if the temp variable is not empty, append its contents to the answer variable. This ensures that the last word which may not end with a space is correctly added to the ans.

C++

Java

Python

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

string ReverseWords(string str)
{
    string ans="";
    string temp="";
    for(int i=str.size()-1; i>=0; i--) {
        if(str[i]==' ' &amp;&amp; temp.empty()) {
            continue;
        } else if(str[i]==' ') {
            ans+=temp+" ";
            temp="";
        } else {
            temp=str[i]+temp;
        }
    }
    if (!temp.empty()) {
        ans+=temp+" ";
    }
    return ans;
}
int main()
{
    string str="  Reverse Words in a   String  ";
    cout<<ReverseWords(str)<<endl;
}

String a in Words Reverse

Time Complexity

We are iterating over array so Time Complexity will be => O(N)

Space Complexity

Since we are not using any extra storage so space complexity will be => O(1)