151. Reverse Words in a String

• Difficulty: Medium

• Topics: String

• Similar Questions:

  • Reverse Words in a String II

Problem:

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.

Solutions:

class Solution {
public:
    string reverseWords(string s) {
        string ret;
        stringstream ss(s);
        string word;

        if (ss >> word) {
            ret.append(word);
        }

        while (ss >> word) {
            ret.push_back(' ');
            ret.append(word);
        }

        if (ret.length() == 0)  return ret;

        // left and right are both facing right
        int left = 0;
        int right = 0;
        while (right < ret.length()) {
            while (right + 1 < ret.length() && ret[right+1] != ' ') ++right;
            stringSwap(ret, left, right);
            right = right + 2;
            left = right;
        }
        stringSwap(ret, 0, ret.length() - 1);
        return ret;
    }

    void stringSwap(string& s, int left, int right) {
        while (left < right) {
            swap(s[left], s[right]);
            ++left;
            --right;
        }
    }
};