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".

Update (2015-02-12):
For C programmers: Try to solve it in-place in O(1) space.

这道题通过率还挺低的，不知道是什么原因，看到这道题还是想着用栈，看到一个空格就入栈，最后出栈加空格，不过用了一些空间，不管了，先试试再说。
我的做法当然没有考虑下面说的用O(1)空间这句话…

class Solution {
public:
    void reverseWords(string &s) {
        int n = s.length();
        stack<string> words;
        int start = 0, l = 0;
        for (int i=0; i<n; i++) {
            int label = false;
            if (s[i] != ' ') {
                start = i;
                i++;
                label = true;
            }
            while (s[i] != ' ' && i < n)
                i++;
            if (label) {
                words.push(s.substr(start, i-start));
            }
        }
        s = "";
        while (!words.empty()) {
            string word = words.top();
            words.pop();
            s += word;
            s += words.empty() ? "" : " ";
        }
    }
};

因为还得考虑到乱入的多个空格，所以还得稍微处理一下，不过还是能过AC的。不过应该还是有更好的办法，看看讨论区吧。
看到一种做法就是先把整个reverse一下，然后再把每一个单词reverse一下，然后就可以了。要注意中间可能是多个空格，所以需要处理一下。下面的做法是把后面的单词往前移，两个单词之间只剩一个空格，再最后把末尾的空格删掉。

class Solution {
public:
    void reverseWords(string &s) {
        reverse(s.begin(), s.end());
        int storeIndex = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] != ' ') {
                if (storeIndex != 0) s[storeIndex++] = ' ';
                int j = i;
                while (j < s.size() && s[j] != ' ') { 
                    s[storeIndex++] = s[j++]; 
                }
                reverse(s.begin() + storeIndex - (j - i), s.begin() + storeIndex);
                i = j;
            }
        }
        s.erase(s.begin() + storeIndex, s.end());
    }
};