题目
给你一个字符串 s，颠倒字符串中单词的顺序。单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。
注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
例：
输入：s = "the sky is blue"
输出："blue is sky the"
方法一：库函数
将字符串分割后翻转输出
class Solution(object):
def reverseWords(self, s):
record = s.split()
return ' '.join(reversed(record))
方法二：不使用辅助空间
删除多余空格，翻转整个字符数组，翻转每个单词
- 删除多余空格。左指针指向首部，右指针指向尾部。首先判断首尾是否存在多余空格，若首部存在多余空格，则左指针向右移动，直至不再存在多余空格；若尾部存在多余空格，则右指针向做移动，直至不再存在多余空格。之后判断中间部分是否存在多余空格，建立临时列表存放除去多余空格后的字符数组，移动左指针，若指向位置不为空格或指向位置为空格但是其前一位不为空格，那么将该位置所对应的值存入列表。
- 翻转字符数组。左指针指向首部，右指针指向尾部。循环，左右指针指向位置的对应值交换，左指针向右移一格，右指针向左移一格
- 翻转单词。通过开端和末端两个指针寻找单词，两个指针的起始位置均为 0。当末端指针指向非空格值时，向右移动，直至指向的位置的值为空格，此时开端指针指向某个单词的第一个字母，而末端指针指向该单词的最后一个字母。通过之前的反转字符数组函数对该字符数组进行翻转，从而得到一个正确的单词。之后，两个指针移向下一个单词的开端，开始新一轮寻找
class Solution(object):
# 删除多余空格
def del_space(self, s):
length = len(s)
left, right = 0, length - 1
temp = []
while left <= right and s[left] == ' ':
left += 1
while left <= right and s[right] == ' ':
right -= 1
while left <= right:
if s[left] != ' ':
temp.append(s[left])
elif s[left] == ' ' and temp[-1] != ' ':
temp.append(s[left])
left += 1
return temp
# 翻转字符数组
def reverse_string(self, nums, left, right):
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
# 翻转单词
def reverse_word(self, nums):
length = len(nums)
start, end = 0, 0
while start < length:
while end < length and nums[end] != ' ':
end += 1
self.reverse_string(nums, start, end - 1)
start = end + 1
end = start
def reverseWords(self, s):
result = self.del_space(s)
self.reverse_string(result, 0, len(result) - 1)
self.reverse_word(result)
return ''.join(result)
相关知识
-
split(sep, num)：
str.split()
分割字符串
sep：分隔符。默认为 None，表示所有空字符，包括空格、换行符“\n”、制表符“\t”等
num：分割次数。默认为没有限制
例：字符串s = " world hello "（前后分别为两个空格
若使用默认的分割方式s.split()，结果为['world', 'hello']
若使用空格进行分割s.split(' ')，结果为['', '', 'world', 'hello', '', ''] -
reversed(seq)：
翻转。
seq：对象。可为列表、元组等
报错
-
can only join in an iterable
list.reverse() 返回值为 None，该结果需使用 print 打印出来
参考
分割：http://c.biancheng.net/view/4276.html
反转：https://wenku.baidu.com/view/2f7e931364ec102de2bd960590c69ec3d5bbdb18.html
代码相关：https://programmercarl.com/0151.%E7%BF%BB%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2%E9%87%8C%E7%9A%84%E5%8D%95%E8%AF%8D.html
