151 Reverse Words in a String

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

Given s = "the sky is blue",
return "blue is sky the".

Clarification:

• What constitutes a word?
  • A sequence of non-space characters constitutes a word.
• Could the input string contain leading or trailing spaces?
  • Yes. However, your reversed string should not contain leading or trailing spaces.
• How about multiple spaces between two words?
  • Reduce them to a single space in the reversed string.

Solution:

class Solution {
public:
    void reverseWords(string &s) {
        vector<string> strs;
        string tmp = "";
        int n = s.size();
        if ( n == 0 ) return;
        for ( int i = 0; i <= n-1; i++ ) {
            if ( s[i] == ' ' and tmp != "" ) {
                strs.push_back(tmp); 
                tmp = ""; 
                continue;
            }
            if ( s[i] != ' ' ) tmp += s[i];
        }
        if ( tmp != "" ) strs.push_back(tmp);
        string res = "";
        if ( strs.size() == 0 ) { s = res;  return;}
        for ( int i = strs.size()-1; i >= 1; i--) { res += strs[i]; res += " ";}
        res += strs[0];
        s = res;
        return;
    }
};

one-pass Solution

class Solution {
public:
    void reverseWords(string &s) {
        int n = s.size();
        if ( n == 0 ) return;
        string tmp = "", res;
        for ( int i = n-1; i >= 0; i-- ) {
            if ( s[i] == ' ' and tmp != "" ) {
                res += tmp + " ";
                tmp = "";
            }
            if ( s[i] != ' ') tmp = s[i] + tmp;
        }
        if ( tmp != "" ) res += tmp;
        if ( res.size() >= 1 and res[res.size()-1] == ' ') s = res.substr(0, res.size()-1);
        else s = res;
        return;
    }
};