字符串中的单词反转

标签: 双指针 字符串

难度: Easy

你在与一位习惯从右往左阅读的朋友发消息，他发出的文字顺序都与正常相反但单词内容正确，为了和他顺利交流你决定写一个转换程序，把他所发的消息 message 转换为正常语序。

注意：输入字符串 message 中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入: message = "the sky is blue"
输出: "blue is sky the"

示例 2：

输入: message = "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：

输入: message = "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

提示：

  • 1 <= message.length <= 10^4
  • message 中包含英文大小写字母、空格和数字
  • message 中至少有一个单词
  •  

注意：

Submission

运行时间: 64 ms

内存: 15.2 MB

class Solution:
    def reverseWords(self, s: str) -> str:
        s = s.strip()
        i = j = len(s) - 1
        res = []
        while i >= 0:
            while i >= 0 and s[i] != ' ':
                i -= 1
            res.append(s[i+1:j+1])
            while s[i] == ' ':
                i -= 1
            j = i
        return ' '.join(res)


if __name__ == '__main__':
    s = Solution()
    s.reverseWords("the sky is blue")

Explain

该题解通过遍历输入字符串，从右到左寻找单词，并逐个添加到结果列表中。首先，使用 strip() 方法去除输入字符串的首尾空格。然后，使用两个指针 i 和 j，初始都指向字符串的最后一个字符。指针 i 向左移动直到找到一个空格，表示一个单词的结束，然后将这个单词添加到结果列表中。接着，跳过中间的所有空格，继续寻找下一个单词。这个过程重复进行，直到遍历完整个字符串。最后，使用 join() 方法将列表中的单词用单个空格连接起来，形成最终的反转后的字符串。

时间复杂度: O(n)

空间复杂度: O(n)

# Solution class to reverse words in a string

class Solution:
    def reverseWords(self, s: str) -> str:
        # Remove leading and trailing spaces
        s = s.strip()
        # Set two pointers at the end of the string
        i = j = len(s) - 1
        res = []
        while i >= 0:
            # Find the start of a word
            while i >= 0 and s[i] != ' ':
                i -= 1
            # Add the word to result
            res.append(s[i+1:j+1])
            # Skip spaces to find the next word
            while i >= 0 and s[i] == ' ':
                i -= 1
            # Set j to the new word's end
            j = i
        # Join all words with a single space
        return ' '.join(res)

Explore

从右向左遍历字符串的主要优势是方便在添加单词到结果列表时实现单词的反转。当从右向左遍历时，我们可以直接按照单词出现的顺序添加到结果列表，而这些单词在最终的输出字符串中将自然地呈现为反转的顺序。如果从左向右遍历，则每次找到一个单词后，需要将其插入到结果列表的开头，这在某些编程语言中可能导致较低的效率，因为插入操作可能涉及数组元素的频繁移动。

在提供的算法中，通过在找到每个单词后使用一个循环来跳过所有连续的空格，确保了下一个单词的搜索从非空格字符开始。这意味着结果列表中添加的每个单词之间原本存在的多余空格都被忽略。最终使用 `join()` 方法连接列表中的单词时，`join()` 自动在每个单词间插入一个单个空格，从而保证了单词之间的分隔恰好只有一个空格，无论原字符串中单词间有多少空格。

这个循环的目的是向左移动指针i，直到找到一个空格字符，这标志着当前单词的开始（左边界）。在这个过程中，指针j保持不变，指向当前单词的结束（右边界）。因此，当循环结束时，i和j之间的部分就是一个完整的单词。这个循环确保了即使单词之间有多个空格，也能准确识别并提取每个单词。

是的，这个设计确实意味着算法效率在一定程度上受到输入字符串中空格数量的影响。这个额外的循环用于跳过单词间的所有空格，以确保下一次迭代能够正确开始于新单词的末尾。如果字符串中空格很多，特别是在单词之间，这将导致额外的迭代和时间消耗。然而，对于大多数实际应用，这种效率的影响通常是可接受的，尤其是考虑到代码的可读性和直观性。