Reserve Words in a String

http://www.cnblogs.com/grandyang/p/4606676.html

Pay attention to the clarification.

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

Idea is to reverse a whole string first and then reverse word one by one. For using C/C++, please use O(1) space

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 cur = i;
                while (cur < s.size() && s[cur] != ' ') {
                    s[storeIndex++] = s[cur++];
                }
                reverse(s.begin() + storeIndex - (cur - i), s.begin() + storeIndex);
                i = cur;
            } 

        }

        s.erase(s.begin()+storeIndex, s.end());
    }     
};