反转字符串中的单词

给你一个字符串 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⁴
• s 包含英文大小写字母、数字和空格 ' '
• s 中至少存在一个单词

解题思路：

从右往左双指针扫描，先跳过空格定位词尾 j，再移动 i 找词头，截取 s[i+1:j+1] 收集单词，最后拼接。

C++

class Solution {
public:
    string reverseWords(string s) {
        int n = s.size();
        string res;
        int i = n - 1;
        while (i >= 0) {
            while (i >= 0 && s[i] == ' ') i--;
            if (i < 0) break;
            int j = i;
            while (i >= 0 && s[i] != ' ') i--;
            if (!res.empty()) res += ' ';
            res += s.substr(i + 1, j - i);
        }
        return res;
    }
};

Java

class Solution {
    public String reverseWords(String s) {
        int n = s.length();
        String res = "";
        int i = n - 1;
        while (i >= 0) {
            while (i >= 0 && s.charAt(i) == ' ') i--;
            if (i < 0) break;
            int j = i;
            while (i >= 0 && s.charAt(i) != ' ') i--;
            if (!res.isEmpty()) res += ' ';
            res += s.substring(i + 1, j + 1);
        }
        return res;
    }
}

Python

from typing import List

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

Go

func reverseWords(s string) string {
    n := len(s)
    res := ""
    i := n - 1
    for i >= 0 {
        for i >= 0 && s[i] == ' ' {
            i--
        }
        if i < 0 {
            break
        }
        j := i
        for i >= 0 && s[i] != ' ' {
            i--
        }
        if res != "" {
            res += " "
        }
        res += s[i+1 : j+1]
    }
    return res
}

时间 O(n)，空间 O(n)。