# 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"
Explanation: Your reversed string should not contain leading or trailing spaces.

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.

Follow up:

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.

# Code (Python)

Approach 1:

Approach 2:

# Code (C++)

Approach 1:

// Concatenate each word reversely.
class Solution {
public:
    string reverseWords(string s) {
        string reversed = "";
        int head = 0;
        int tail = 0;
        while (head < s.size() && tail <= s.size())
        {
            if (s[head] == ' ')
                head++;
            else if (tail == s.size() || s[tail] == ' ')
            {
                string word = s.substr(head, tail - head);
                reversed = word + " " + reversed;
                head = tail + 1;
            }
            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) {
        while (head < tail)
        {
            std::swap(s[head], s[tail]);
            head++;
            tail--;
        }
    }
public:
    string reverseWords(string s) {
        // Reverse the while sentence.
        reverseString(s, 0, s.size() - 1);
        // Reverse each word.
        int head = 0;
        int tail = 0;
        while (head < s.size() && tail <= s.size())
        {
            if (s[head] == ' ')
                head++;
            else if (tail == s.size() || s[tail] == ' ')
            {
                reverseString(s, head, tail - 1);
                head = tail + 1;
            }
            tail++;
        }
        // Remove duplicated zeros.
        head = 0;
        tail = 0;
        while (tail < s.size())
        {
            if (s[tail] != ' ')
            {
                s[head] = s[tail];
                head++;
            }
            else if (tail > 0 && s[tail-1] != ' ')
            {
                s[head] = ' ';
                head++;
            }
            tail++;
        }
        if (head > 0 && s.size() > 0 && s[s.size()-1] == ' ')
            head--;
        return s.substr(0, head);
    }
};