给定一个字符串,逐个翻转字符串中的每个单词。
示例 1:
输入: "the sky is blue"
输出: "blue is sky the"
示例 2:
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。
示例 3:
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。
思路:
先不管每个单词中字母的顺序是否是正确的,我们先让单词与单词之间的相对位置都是正确的。
先把整个字符串全部反转一下。
然后再把每个单词的里面都进行一次反转(每个单词都被空格隔出来了)
(注意:其实如果使用库函数,可以直接split,拆成一个个单词,再把单词倒序放入新的list,再变成str,但是这样就起不到练习题的效果了,所以这里不用这种简单的方法)
反转后,还需要移除空格。
如果使用for循环遍历,然后遇到空格就使用erase函数去移除,这个时间复杂度是O(n^2), 因为erase函数的时间复杂度是O(n)
Python实现:
上面的思路是C++的思路,但是Python有更简便的方法(不过大体思路还是相似的)
方法一:
先删除空白,然后整个反转,最后单词反转。 因为字符串是不可变类型,所以反转单词的时候,需要将其转换成列表,然后通过join函数再将其转换成列表,所以空间复杂度不是O(1)
s.strip() 这个函数可以删掉str头部和尾部的空白。注意,strip()函数并不直接改变原来的str,而是生成新的str。str是不可改变的。
代码:
class Solution:
def reverseWords(self, s: str) -> str:
s = s.strip()
s = s[::-1]
return ' '.join(word[::-1] for word in s.split())
但是这道题似乎不需要先用strip函数删除前后空白,因为s.split()就是把单词拿出来,放入list,前后的空格就没有了。
可以改成:
class Solution:
def reverseWords(self, s: str) -> str:
s = s[::-1]
return ' '.join(word[::-1] for word in s.split())
方法二:使用双指针
思路:
先用split函数把s中的单词拿出来,放入list。
使用left和right指针,从左和右遍历list里的元素,即单词,反转。
然后再把list变成str,用' '.join( )
代码:
class Solution:
def reverseWords(self, s: str) -> str:
words = s.split()
left = 0
right = len(words)-1
while left < right:
words[left], words[right] = words[right], words[left]
left += 1
right -= 1
return ' '.join(words)