题目描述

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

示例 1：
输入: “the sky is blue”
输出: “blue is sky the”

示例 2：
输入: “  hello world!  “
输出: “world! hello”
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：
输入: “a good   example”
输出: “example good a”
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

思路解析

这道题的第一个难点是翻转，之前只接触过将字符串从头到尾翻转，但是如何以单词为基本单位进行翻转呢？

很自然地想到可以用翻转再翻转的方式处理，即先把每一个单词翻转，对于 the sky is blue 来说， 翻转成为 eht yks si eulb，然后再整体进行翻转，就得到了 blue is sky the这种形式。其实这种在数组中分块移动的方法非常常用，是一种固定的套路，也被称为左/右旋。

1
2
3
4
5
6
7
8
9
10
11
12
int st = 0, ed=0;
while (st < s.size()){
	// 翻转每一个单词
	while (ed < s.length() && s.at(ed) != ' ')
		ed++;
	reverse(s.begin() + st, s.begin() + ed);
	// 略去空格
	while (ed < s.length() && s[ed]==' ')  ed++;
	st = ed;
}
// 整体翻转
reverse(s.begin(), s.end());

通过上面的操作，就可以得到一个初具雏形的答案了，但是还不够，有下面的问题存在。

  1. 上面的代码只是把所有的字符串重新排布好了，首尾的空格并没有清理掉。
  2. 词与词之间的空格可能有多个的情况需要处理。

针对上面的情况，我们需要删掉字符串中的首尾空格和句中重复空格，最后得到现在的字符串的子集，所以我们可以用移除元素的方法，以O(n)的时间复杂度，O(1)的空间复杂度完成这件事情。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int j = 0;
st = 0,ed = s.length() - 1;
// 除去首尾空格
while (s[st]==' ')  st++;
while (s[ed]==' ')  ed--;
int t = st;

for (;st<=ed;st++){
	// 移除词间重复的空格,经典的在第一个位置不作判断，而是从第二个位置开始，但是这里其实没必要引入t，st > 0就可以了
	// 因为当st == t时s[st] != ' '恒成立（除去字符串本来就是空，那根本不会进行这个判断）
	if (st > t && s[st]==' '&&s[st-1]==' ')   continue;
	s[j++]=s[st];
}
// 重新调整字符串大小
s.resize(j);

我们重新定义一个覆盖指针j，根据满足要求的情况覆盖式地更新原字符串即可，这个过程中不会影响st空格的判断，因为j始终比st慢。
最后j就是新字符串的长度，我们用resize方法更新字符串长度即可。

总结

这个题主要考察双指针思想的理解，翻转操作利用的是相向指针，而移除空格，原地覆盖利用的是快慢指针。还有reverse(iter, iter)，str.resize(size)库函数的使用。除此之外还有两批次翻转（左旋/右旋）的思想。