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

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

click to show clarification.

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.

本题较为复杂，主要在于可能会存在前缀或者多个连在一起的空格，此时要删去多余的空格，这就需要我们用一个cur指针指向新数组的遍历位置，然后一个一个往前复制。

反转可以分为两步，第一步先将整个数组反转，第二步为将每个单词单独反转，则可得到结果。

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