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

题目描述

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

示例：
输入：”Let’s take LeetCode contest”
输出：”s’teL ekat edoCteeL tsetnoc”

思路

1.将字符串按照空格划分开得到字符串中的每一个单词,然后将每个单词反转
，在将反转后的所有单词用空格拼接起来
2.使用额外空间
开辟一个新字符串。然后从头到尾遍历原字符串，直到找到空格为止，此时找到了一个单词，并能得到单词的起止位置。随后，根据单词的起止位置，可以将该单词逆序放到新字符串当中。如此循环多次，直到遍历完原字符串，就能得到翻转后的结果。
3.原地解法
此题也可以直接在原字符串上进行操作，避免额外的空间开销。当找到一个单词的时候，我们交换字符串第一个字符与倒数第一个字符，随后交换第二个字符与倒数第二个字符……如此反复，就可以在原空间上翻转单词。
需要注意的是，原地解法在某些语言（比如 Java，JavaScript，python）中不适用，因为在这些语言中 String 类型是一个不可变的类型。
在python中可以先将字符串转为列表然后进行算法设计。

更多思路参考“一行流”，简直牛逼！！！

代码

class Solution:
    def reverseWords(self, s: str) -> str:
        """
        将字符串按照空格划分开得到字符串中的每一个单词
        将每个单词反转
        将反转后的所有单词用空格拼接起来
        """
        words = s.split(' ')
        reversed_words = []
        for word in words:
            reversed_words.append(self.reverseStr(word))
        return ' '.join(reversed_words)

    def reverseStr(self, s: str) -> str:
        s = list(s)
        s[:] = s[::-1]
        return ''.join(s)

    def reverseWords2(self, s: str) -> str:
        """使用额外空间"""
        ret = ''
        length = len(s)
        i = 0
        while i < length:
            start = i
            # 遍历字符串找到空格位置（找到了一个单词）
            while i < length and s[i] != ' ':
                i += 1
            # 根据单词的起止位置，可以将该单词逆序放到新字符串当中
            for p in range(start, i):
                ret += s[start + i - 1 - p]
            # 拼上单词后的空格
            while i < length and s[i] == ' ':
                i += 1
                ret += ' '

        return ret

    def reverseWords3(self, s: str) -> str:
        s = list(s)  # python中字符串为不可变类型，不支持原地修改，可转列表
        length = len(s)
        i = 0
        while i < length:
            start = i

            while i < length and s[i] != ' ':
                i += 1

            left = start
            right = i - 1
            while left < right:
                s[left], s[right] = s[right], s[left]
                left += 1
                right -= 1

            while i < length and s[i] == ' ':
                i += 1
        return ''.join(s)


if __name__ == "__main__":
    slt = Solution()
    s = "Let's take LeetCode contest"
    res = slt.reverseWords3(s)
    print("反转单词后的字符串：", res)

victory的博客

leetcode | 557.反转字符串中的单词3

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

题目描述

思路

代码