0151-leetcode算法实现之翻转字符串里的单词-reverse-words-in-a-string-python&golang实现

本文主要是介绍0151-leetcode算法实现之翻转字符串里的单词-reverse-words-in-a-string-python&golang实现，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

给你一个字符串 s ，逐个翻转字符串中的所有 单词 。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。

说明：

输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
翻转后单词间应当仅用一个空格分隔。
翻转后的字符串中不应包含额外的空格。

示例 1：

输入：s = "the sky is blue"
输出："blue is sky the"
示例 2：

输入：s = "  hello world  "
输出："world hello"
解释：输入字符串可以在前面或者后面包含多余的空格，但是翻转后的字符不能包括。
示例 3：

输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，将翻转后单词间的空格减少到只含一个。
示例 4：

输入：s = " Bob Loves Alice "
输出："Alice Loves Bob"
示例 5：

输入：s = "Alice does not even like bob"
输出："bob like even not does Alice"

提示：

1 <= s.length <= 104
s 包含英文大小写字母、数字和空格 ' '
s 中 至少存在一个 单词

进阶：

请尝试使用 O(1) 额外空间复杂度的原地解法。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-words-in-a-string

python

# 翻转字符串里的单词
class Solution:
    def reverseWords(self, s: str) -> str:
        """
        双指针，字符串的综合操作
        解题思路如下：
        -移除多余空格
        -将整个字符串反转
        -将每个单词反转
        :param s:
        :return:
        """
        l = self.rmExtraSpaces(s) # 1.删除多余空格
        self.reverseStrs(l, 0, len(l) - 1) # 2.翻转字符
        self.reverseEachWord(l) # 3.翻转每个单词
        return ''.join(l)

    # 1.去除头中尾空格
    def rmExtraSpaces(self, s):
        n = len(s)
        left = 0
        right = n - 1
        # rm开头空格
        while left <= right and s[left] == ' ':
            left += 1
        # rm结尾空格
        while left <= right and s[right] == ' ':
            right -= 1
        # rm串中多余空格
        tmp = []
        while left <= right:
            if s[left] != ' ':
                tmp.append(s[left])
            # 当前位置是空格，但是相邻的上一个位置不是空格，则该空格是合理的
            elif tmp[-1] != ' ':
                tmp.append(s[left])
            left += 1
        return tmp

    # 2.翻转字符数组
    def reverseStrs(self, strs, left, right):
        while left < right:
            strs[left], strs[right] = strs[right], strs[left]
            left += 1
            right -= 1
        return None

    # 3.翻转每个单词
    def reverseEachWord(self, strs):
        start, end = 0, 0
        n = len(strs)
        while start < n:
            while end < n and strs[end] != ' ':
                end += 1
            self.reverseStrs(strs, start, end-1)
            start = end + 1
            end += 1
        return None




if __name__ == "__main__":
    str1 = "it is raining today"
    str2 = " roast pork is very  yummy "
    test = Solution()
    print(test.reverseWords(str1))
    print(test.reverseWords(str2))

golang

这篇关于0151-leetcode算法实现之翻转字符串里的单词-reverse-words-in-a-string-python&golang实现的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！