101.翻转字符串里的单词

题号151：

给定一个字符串，逐个翻转字符串中的每个单词。

示例:

输入: "the sky is blue",

输出: "blue is sky the".

说明:

无空格字符构成一个单词。

输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

进阶: 请选用C语言的用户尝试使用 O(1) 空间复杂度的原地解法。

解题思路：

先不考虑空格：逐个翻转单词，最后对整个字符串进行一次翻转，即可得到正确结果；

考虑空格，使用辅助空间，空间复杂度O(n)：遍历字符串，若遇到连续空格，则跳过，否则将字符依次保存到新字符串中。

优化思考：若不借助辅助空间，如何在翻转过程中处理多余空格？

可以设置一个变量，指向实际字符串（即没有多余空格的字符串）当前位置，当遇到多余空格时，实际字符串位置不动，只在遇到非空格字符时继续向前赋值，并在单词之间加空格。

代码实现：

class Solution {

public:

void reverseWords(string &s) {

if(s.length()){

int j=0;

for(int i=0;i

while(i

i++;// 跳过空格

}

int count=0;

if(j>0 && i

// 单词前需要加一个空格；（对整个字符串翻转后空格会在单词之后

// 第一个单词（j==0）前面不需要空格；（对整个字符串翻转后第一个单词会变成最后一个，即最后一个单词后面不需要空格

//i==s.length()，遍历结束

s[j++]=' ';

}

while(i

s[j++]=s[i++];

count++;

}

// 逐个翻转单词

reverse(s.begin()+j-count,s.begin()+j);

}

// 去掉多余字符

s.resize(j);

// 最后翻转整个字符串

reverse(s.begin(),s.end());

}

}

};