151. 反转字符串中的单词

1. 题目

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

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

示例 1：

1
2
输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

1
2
3
输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

1
2
3
输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

提示：

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

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

2. 思路

  • 初始化stack栈变量，将解析出来的每个单词放入该栈中（目的是体现出栈的先进后出特性来生成最终的答案）

  • 初始化word可变字符串变量，目的是作为解析字符串的容器，同时转换字符串s为字符数组ch，并对该数组进行遍历

  • 在遍历ch数组的过程中：

    • 如果遇到字符为空格，同时word字符串容器中已存储单词，则将该单词放入stack栈中，并重置word变量
    • 如果遇到字符不为空格，则将该字符追加入word字符串容器中

  • 遍历完ch数组后，需要判断word容器中是否有存在单词，如果存在则补充追加至stack栈中

  • 遍历stack栈中收集到的单词，以此形成反序排列，此过程中需要在单词与单词中加入空格

  • 输出结果前需要处理好最后一个单词后的多余空格

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public String reverseWords(String s) {
        Deque<String> stack = new ArrayDeque<>();

        var ch = s.toCharArray();
        var word = new StringBuilder();
        var result = new StringBuilder();

        for (var i = 0; i < ch.length; ++i) {
            if (ch[i] != ' ') {
                word.append(ch[i]);
            } else if (word.length() > 0) {
                stack.push(word.toString());
                word = new StringBuilder();
            }
        }

        if (word.length() > 0) {
            result.append(word).append(' ');
        }

        while (!stack.isEmpty()) {
            result.append(stack.pop()).append(' ');
        }

        return result.deleteCharAt(result.length() - 1).toString();
    }
}

4. 复杂度

  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

image-20230805172157492