151. Reverse Words in a String

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 at least one space.

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

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

Input: s = "the sky is blue"
Output: "blue is sky the"

Example 2:

Input: s = "  hello world  "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: s = "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Example 4:

Input: s = "  Bob    Loves  Alice   "
Output: "Alice Loves Bob"

Example 5:

Input: s = "Alice does not even like bob"
Output: "bob like even not does Alice"

Constraints:

1 <= s.length <= 104
s contains English letters (upper-case and lower-case), digits, and spaces ' '.
There is at least one word in s.

Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?

Steps to Solve

We can make a stack and start from the beginning of the given string.
We also have to remove the extra spaces so for that we make a while loop and if we get extra space we just move forward.
We make a string word to store the current word.
We make another while loop. If we get a space it means the current word has ended and now we can push it into our stack.
Else we add s[i] to the current word.
After the for loop gets over, we can now make our answer using the elements in the stack.
We make a string ans to store our answer.
If ans is empty then we store the top of the stack else we add a space and then store the top and then pop out the stack once to remove the top element.
Our ans is complete and we can return it.

Solution 1 using Stack

class Solution {

public:

    string reverseWords(string s) {

        stack <string> st;

        for(int i=0; i<s.length(); i++){

            while(s[i]==' '){

                i++;

}

            string word="";

            while (s[i]!=' ' && i<s.length()){

                if(s[i]==' '){

                    break;

}

                else{

                word+=s[i];

}

                i++;

}

            st.push(word);

}

        string ans="";

        while(!st.empty()){

            if(ans==""){

                ans=st.top();                                                          

                st.pop();

}

            else{

                ans=ans+' '+st.top();

            st.pop();

}

}

        return ans;

}

};

Solution 2

class Solution
{
public:
    string reverseWords(string s)
    {
        vector<string> v;
        string ans = "";
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] != ' ')
            {
                ans += s[i];
            }
            else
            {
                if (ans.size() != 0)
                    v.push_back(ans);
                ans = "";
            }
        }
        if (ans.size() != 0)                                                           
            v.push_back(ans);
        ans = "";
        for (int i = v.size() - 1; i > 0; i--)
        {
            ans += (v[i]);
            ans += ' ';
        }
        ans += v[0];
        return ans;
    }
};

How to reverse a string in C++?

Ans- We can reverse a string in C++ using the help of a stack or vector. We can simply store the words from end of the string and then again make a new string and simply return the answer.

151. Reverse Words in a String