[LeetCode] Reverse Words in a String

Problem Statement (link here):

Given an input string, reverse the string word by word.
For example,
Given s = "the sky is blue",
return "blue is sky the".

Analysis:
The problem statement is quite simple, the two tasks are 1) detect a word; 2) reverse the word.

For 1), I choose to scan char by char, once I found a space, the scanned chars form a word;
For 2), there may be a couple of choices, you could start construct a new string - let's say s1, concatenate the new word with s1 each time you found a word. Or, you could use a stack to store all the words, and once scanning s finishes, we pop out stack one after another and form a reversed string. For both methods, the time complexity is O(n), space complexity is O(n), where n is length of the string s.

For step 2), I take the stack approach.

Code:

class Solution {
public:
    void reverseWords(string &s) {
        if (s.empty()) return;
        stack<string> rev;
        int len = s.length();
        string word = "";
        for (int i = 0; i < len+1; i++) {
            string t = s.substr(i, 1);
            if (!word.empty() && (t.compare(" ") == 0 || i == (len))) {
                rev.push(word);
                word = "";
            }
            else if (t.compare(" ") != 0)
                word = word + t;
        }
        s = "";
        while(!rev.empty()) {
            s = s + rev.top() + " ";
            rev.pop();
        }
        // remove spaces from the end
        if (!s.empty()) {
            string x = s.substr(s.length()-1, 1);
            while(x == " ") {
                s = s.substr(0, s.length()-1);
                x = s.substr(s.length()-1, 1);
            }
        }
    }
};