力扣刷题-字符串-翻转字符串中的单词

151.翻转字符串里的单词

给定一个字符串，逐个翻转字符串中的每个单词。
示例 1：
输入: “the sky is blue”
输出: “blue is sky the”
示例 2：
输入: " hello world! "
输出: “world! hello”
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入: “a good example”
输出: “example good a”
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

思路

首先题目说了，输入字符串可以在前面/后面有多余的空格，而输出不行，所以必须先删除输入字符串前后面多余的空格（这就很容易想到python的strip函数），然后第二步可以把整个字符串翻转，但这样内部单词每个字符也翻转了，所以还需要将内部单词再翻转一遍。如何实现？可以split分割啊，因为单词与单词之间肯定是按空格分割的，所以先分出单独的单词，然后对每个单词翻转。
先整体翻转再局部翻转

解法一

如果是定义一个列表来获取单个单词，这样空间复杂度就是O(n)了。

class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        # 第一步：先去除字符串前面/后面的空格
        s = s.strip() # 删除空格
        # 第二步：反转字符串
        s = s[::-1] # 反转字符串
        # 第三步：反转每一个单词
        result = [] # 这样的话就不是原地操作了 而是由O(n)的空间复杂度
        x = s.split() # 按空格分割
        for i in range(len(x)):
            result.append(x[i][::-1])
        return ' '.join(result)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

解法二

如何原地操作？——>其实就可以将以上代码整合为一行

class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        # 第一步：先去除字符串前面/后面的空格
        s = s.strip() # 删除空格
        # 第二步：反转字符串
        s = s[::-1] # 反转字符串
        # 第三步：反转每一个单词
        result = ' '.join(word[::-1] for word in s.split()) # 列表推导式
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13

解法三 双指针法

这里双指针本质上是与反转字符串中一致，但是这里是将整个单词看成整体。——>思维打开！

# 双指针法
class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        s = s.strip() # 删除空格
        words = s.split() # 构成单词列表 然后将单词看成整体 进行单词的翻转
        left = 0
        right = len(words) - 1
        while left < right:
            tmp = words[left]
            words[left] = words[right]
            words[right] = tmp
            left += 1 # 细心
            right -= 1
        return ' '.join(words) # 因为最终需要的是字符串       
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18