Medium

题目描述

给你一个字符串 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"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到只含一个。

提示：

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

**进阶：**如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。

解题思路

解题思路

这道题要求我们翻转字符串中单词的顺序，同时处理多余的空格。有几种主要的解法：

方法一：使用内置函数（推荐）

利用语言内置的字符串分割和翻转功能：

  1. 使用 split() 按空格分割字符串，自动过滤空字符串
  2. 翻转分割后的单词数组
  3. 用单个空格连接所有单词

方法二：双指针解法

更符合算法思维的解法：

  1. 从右向左遍历字符串，用双指针找到每个单词
  2. 跳过空格，找到单词的右边界和左边界
  3. 将找到的单词添加到结果中

方法三：原地算法（进阶）

对于可变字符串的语言：

  1. 先移除多余空格
  2. 翻转整个字符串
  3. 再翻转每个单词

虽然题目提到了进阶要求，但在实际面试中，方法一的简洁性和可读性更受欢迎，是最推荐的解法。

代码实现

class Solution {
public:
    string reverseWords(string s) {
        vector<string> words;
        int n = s.length();
        int i = 0;
        
        // 提取所有单词
        while (i < n) {
            // 跳过空格
            while (i < n && s[i] == ' ') i++;
            if (i >= n) break;
            
            // 找到单词
            int start = i;
            while (i < n && s[i] != ' ') i++;
            words.push_back(s.substr(start, i - start));
        }
        
        // 反向连接单词
        string result;
        for (int j = words.size() - 1; j >= 0; j--) {
            result += words[j];
            if (j > 0) result += " ";
        }
        
        return result;
    }
};

class Solution:
    def reverseWords(self, s: str) -> str:
        # 方法一：使用内置函数（推荐）
        return ' '.join(s.split()[::-1])
        
        # 方法二：双指针解法
        # words = []
        # i = 0
        # n = len(s)
        
        # while i < n:
        #     # 跳过空格
        #     while i < n and s[i] == ' ':
        #         i += 1
        #     if i >= n:
        #         break
        #     
        #     # 找到单词
        #     start = i
        #     while i < n and s[i] != ' ':
        #         i += 1
        #     words.append(s[start:i])
        
        # return ' '.join(words[::-1])

public class Solution {
    public string ReverseWords(string s) {
        // 分割字符串并过滤空字符串
        string[] words = s.Split(' ', StringSplitOptions.RemoveEmptyEntries);
        
        // 反转数组
        Array.Reverse(words);
        
        // 用空格连接
        return string.Join(" ", words);
    }
}

var reverseWords = function(s) {
    // 方法一：使用内置函数（推荐）
    return s.trim().split(/\s+/).reverse().join(' ');
    
    // 方法二：双指针解法
    // const words = [];
    // let i = 0;
    // const n = s.length;
    
    // while (i < n) {
    //     // 跳过空格
    //     while (i < n && s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
内置函数解法O(n)O(n)
双指针解法O(n)O(n)
原地算法O(n)O(1)

说明：

  • 时间复杂度：所有方法都需要遍历整个字符串，因此时间复杂度为 O(n)
  • 空间复杂度：除了原地算法外，其他方法都需要额外存储单词，空间复杂度为 O(n)；原地算法可以达到 O(1) 空间复杂度

相关题目