151

151. Reverse Words in a String (Medium)

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

Example:  

Input: "the sky is blue",
Output: "blue is sky the".

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) space.

Companies:
Microsoft, Facebook, Bloomberg, Goldman Sachs, Walmart Labs, Nvidia, Cisco

Related Topics:
String

Similar Questions:

• Reverse Words in a String II (Medium)

Solution 1.

// OJ: https://leetcode.com/problems/reverse-words-in-a-string/
// Author: github.com/lzl124631x
// Time: O(S)
// Space: O(1)
class Solution {
public:
    void reverseWords(string &s) {
        int i = 0, j = 0;
        while (j < s.size()) {
            while (j < s.size() && s[j] == ' ') ++j;
            if (i != 0 && j != s.size()) s[i++] = ' ';
            while (j < s.size() && s[j] != ' ') s[i++] = s[j++];
        }
        s.erase(i);
        i = j = 0;
        while (i < s.size()) {
            j = i;
            while (j < s.size() && s[j] != ' ') ++j;
            reverse(s.begin() + i, s.begin() + j);
            i = j + 1;
        }
        reverse(s.begin(), s.end());
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/reverse-words-in-a-string/
// Author: github.com/lzl124631x
// Time: O(S)
// Space: O(S)
class Solution {
public:
    string reverseWords(string s) {
        string ans;
        for (int i = s.size() - 1; i >= 0;) {
            while (i >= 0 && s[i] == ' ') --i;
            if (i < 0) break;
            if (ans.size()) ans += ' ';
            int j = i;
            while (j >= 0 && s[j] != ' ') --j;
            for (int k = j + 1; k <= i; ++k) ans += s[k];
            i = j;
        }
        return ans;
    }
};

Solution 3.

// OJ: https://leetcode.com/problems/reverse-words-in-a-string/
// Author: github.com/lzl124631x
// Time: O(S)
// Space: O(S)
class Solution {
public:
    string reverseWords(string s) {
        istringstream ss(s);
        string word, ans;
        while (ss >> word) {
            reverse(word.begin(), word.end());
            if (ans.size()) ans += ' '; 
            ans += word;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

Solution 4.

// OJ: https://leetcode.com/problems/reverse-words-in-a-string/
// Author: github.com/lzl124631x
// Time: O(S)
// Space: O(S)
class Solution {
public:
    string reverseWords(string s) {
        istringstream ss(s);
        string word, ans;
        while (ss >> word) {
            if (ans.size()) word += " ";
            ans = word + ans;
        }
        return ans;
    }
};