0151-leetcode算法实现之翻转字符串里的单词-reverse-words-in-a-string-python&golang实现(0151 leetcode algorithm to flip the words in the string – reverse-words-in-a-string-python & golang implementation)

给你一个字符串 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

————————

Give you a string s and flip all the words in the string one by one.

A word is a string of non whitespace characters. Use at least one space in s to separate words in the string.

Please return a string that flips the word order in S and connects it with a single space.

explain:

The input string s can contain extra spaces before, after, or between words.
After flipping, the words should be separated by only one space.
The flipped string should not contain additional spaces.

Example 1:

Input: S = “the sky is blue”
Output: “blue is sky the”
Example 2:

Input: S =“   hello world  ”
Output: “World Hello”
Explanation: the input string can contain extra spaces before or after, but the flipped characters cannot be included.
Example 3:

Enter: S = “a good”   example”
Output: “example good a”
Explanation: if there is extra space between two words, reduce the space between words after flipping to only one.
Example 4:

Enter: S = “Bob loves Alice”
Output: “Alice loves Bob”
Example 5:

输入:s = “Alice does not even like bob”
输出:”bob like even not does Alice”

Tips:

1 <= s.length <= one hundred and four
S contains English upper and lower case letters, numbers and spaces’
At least one word exists in S

Advanced:

Please try using   O (1) in situ solution of additional space complexity.

来源:力扣(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