## # 151. Reverse Words in a String

Given an input string, reverse the string word by word.

Example 1:

``````Input: "the sky is blue"
Output: "blue is sky the"
``````

Example 2:

``````Input: "  hello world!  "
Output: "world! hello"
``````

Example 3:

``````Input: "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.
``````

Note:

• A word is defined as a sequence of non-space characters.
• Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
• You need to reduce multiple spaces between two words to a single space in the reversed string.

For C programmers, try to solve it in-place in O(1) extra space.

### # Solution

Approach 1: Concatenate each word reversely.

Approach 2: In-place: first reverse the whole sentence and then reverse each word.

Approach 1:

Approach 2:

### # Code (C++)

Approach 1:

``````// Concatenate each word reversely.
class Solution {
public:
string reverseWords(string s) {
string reversed = "";
int tail = 0;
while (head < s.size() && tail <= s.size())
{
else if (tail == s.size() || s[tail] == ' ')
{
reversed = word + " " + reversed;
}
tail++;
}
return reversed.substr(0, reversed.size() - 1);
}
};
``````

Approach 2:

``````// In-place: first reverse the whole sentence and then reverse each word.
class Solution {
private:
void reverseString(string& s, int head, int tail) {
{
tail--;
}
}
public:
string reverseWords(string s) {
// Reverse the while sentence.
reverseString(s, 0, s.size() - 1);
// Reverse each word.
int tail = 0;
while (head < s.size() && tail <= s.size())
{
else if (tail == s.size() || s[tail] == ' ')
{
}
tail++;
}
// Remove duplicated zeros.
tail = 0;
while (tail < s.size())
{
if (s[tail] != ' ')
{
}
else if (tail > 0 && s[tail-1] != ' ')
{