翻转字符串里的单词【LeetCode 151】

题目描述：

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

说明：

无空格字符构成一个 单词 。 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

请尝试使用 O(1) 额外空间复杂度的原地解法。

分析：

对于一个字符数组的O(1)翻转，我们可以直接用一个for循环，应该是比较好想到的。

void reverseString(vector<char>& s) { int l=s.size(); for (int i=0; i<l/2; i++) swap(s[i],s[l-i-1]); }

那么现在扩展到字符串了，我们可不可以根据字符的方法，找到字符串中的每个单词，然后再swap交换呢？

乍一想确实没啥毛病，但是操作起来会发现，字符都是一个，交换没难度，但是单词的长度不一，换起来是很麻烦的，交换完之后，指针的维护也很麻烦，所以不好整。

巧妙的做法：先将字符串整体翻转，再翻转每个单词即可。

字符串整体翻转，我们想实现的单词位置交换实现了，就是单词逆序了而已，在这个基础上再翻转一个单词，那就变成了一个字符数组的交换问题，就比较容易了。

代码：

class Solution { public: string reverseWords(string s) { reverse(s.begin(),s.end()); //整体翻转 int i=0; //翻转每个单词 while (i<s.size()){ if (s[i]!=' ') { int start=i; while (i<s.size() && s[i]!=' ') i++; reverse(s.begin()+start,s.begin()+i); } else i++; } i=0; //开头的多余空格 while (i<s.size() && s[i]==' ') i++; s.erase(0,i); i=s.size()-1; //结尾的多余空格 while (i>=0 && s[i]==' ') i--; s.erase(i+1,s.size()-i-1); i=0; //中间的多余空格 while (i<s.size()){ if (s[i]==' ' && s[i-1]==' ') s.erase(i-1,1); else i++; } return s; } };

使用了C++的string类中两个函数：

第一个是交换函数 reverse( ，);         reverse(  s.begin( ) , s.end( ) );     翻转整个s     reverse(  s.begin( ) +l , s.begin( ) + r);  翻转从[ l, r) 的区间，注意不包括 r 。 其中begin end是返回的指针iterator，可以用加减整数的方式控制位置。

第二个是删除函数 erase( );     s.erase( i , x ) ;   在字符串s中从第i个位置删除x个字符（删除包括 i 本身）