题目链接-来源：力扣（LeetCode）

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student. “，则输出”student. a am I”。

示例 1：

输入: “the sky is blue”
输出: “blue is sky the”

思路：

用一前一后两个指针 left 和 right 遍历字符串。同时用 StringBuilder 将收集到的单词（即 left 与 right 形成的子串）插入头部，并用空格隔开即可。
对于 left，我们要为其安排一个合适的停止位置（某个单词的起始位置），之后 right 从 left 出发，达到一个合适的停止位置（该单词的结束位置）。
可以通过如下规则安排指针的行动， left 和 right 初始化为 0。

  • 当前为空格，left 和 right 同时前进。
  • 当前为字符，left 停止，right 前进直到碰见空格。复制 left 和 right 间的子串进入 StringBuilder 的开头处。
    细节处理，原字符串第一个单词前（生成的字符串最后一个单词的末尾）不需要加空格，之后的每个单词插入前都要先添一个空格。可以用一个 flag 变量控制。
    时间复杂度：O(n)
    空间复杂度：O(n)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = new StringBuilder();
        int n = s.length();
        boolean firstWord = false;
        for (int left = 0, right = 0; left < n;) {
            if (s.charAt(left) == ' ') {
                left++;
                right++;
            } else {
                while (right < n && s.charAt(right) != ' ') {
                    right++;
                }
                if (firstWord) {
                    sb.insert(0, ' ');
                }
                firstWord = true;
                sb.insert(0, s.substring(left, right));
                left = right;
            }
        }
        return sb.toString();
    }
}