翻转单词
题目描述
给定一个字符串,逐个翻转字符串中的每个单词。
示例 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 | int st = 0, ed=0; |
通过上面的操作,就可以得到一个初具雏形的答案了,但是还不够,有下面的问题存在。
- 上面的代码只是把所有的字符串重新排布好了,首尾的空格并没有清理掉。
- 词与词之间的空格可能有多个的情况需要处理。
针对上面的情况,我们需要删掉字符串中的首尾空格和句中重复空格,最后得到现在的字符串的子集,所以我们可以用移除元素的方法,以O(n)的时间复杂度,O(1)的空间复杂度完成这件事情。
1 | int j = 0; |
我们重新定义一个覆盖指针j,根据满足要求的情况覆盖式地更新原字符串即可,这个过程中不会影响st空格的判断,因为j始终比st慢。
最后j就是新字符串的长度,我们用resize方法更新字符串长度即可。
总结
这个题主要考察双指针思想的理解,翻转操作利用的是相向指针,而移除空格,原地覆盖利用的是快慢指针。还有reverse(iter, iter)
,str.resize(size)
库函数的使用。除此之外还有两批次翻转(左旋/右旋)的思想。