LeetCode 557. 反转字符串中的单词 III | Python

557. 反转字符串中的单词 III

题目

给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例：

输入："Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc"

提示：

在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。

解题思路

使用辅助列表

先看题目，给定字符串，其中字符串含有空格，要求反转被空格隔开的单词，但是保留空格和单词的初始顺序。

再看后面的提示，字符串每个单词只有单个空格分隔，字符串不会有其他额外的空格。

因为只有单个空格分隔，那么这里，我们可以考虑将给定的字符串按照空格进行分割，这里使用字符串的 split() 函数，具体的做法：

按照空格对字符串进行分割；
定义辅助列表，然后将分割部分的单词进行翻转，按照顺序添加到辅助列表中；
最后将反转之后单词进行拼接，添加空格间隔。

具体代码实现如下：

class Solution:
    def reverseWords(self, s: str) -> str:
        # 按照空格进行切割
        s = s.split(' ')
        # 然后将切割后的每部分都进行翻转
        ans = []
        for part in s:
            part = part[::-1]
            ans.append(part)

        # 最后拼接
        return ' '.join(ans)

前面的方法使用字符串的 split() 方法，这里再说一种在不使用分割的方法如何实现：

遍历字符串，定义变量 left, right 分别指向单词开始和结尾，定义辅助列表；
移动 right，查找空格，当遇到空格时，开始逆序将单词添加到辅助列表中；
然后遇到空格，也将空格添加到辅助列表，再次移动 right，重复前面的步骤，直至 right 到达字符串末尾。

具体的代码实现如下。

class Solution:
    def reverseWords(self, s: str) -> str:
        ans = []
        length = len(s)
        
        right = 0
        while right < length:
            left = right
            # 先寻得空格，然后对空格前面进行交换
            while right < length and s[right] != ' ':
                right += 1
            # 逆序添加到辅助列表中
            for i in range(right-1, left-1, -1):
                ans.append(s[i])
            # 遇到空格也将空格也添加到列表中，然后继续移动
            while right < length and s[right] == ' ':
                ans.append(' ')
                right += 1
        
        # 返回
        return ''.join(ans)