题目描述

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

示例 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)库函数的使用。除此之外还有两批次翻转(左旋/右旋)的思想。