题目链接

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

思路

这道题初看题目觉得非常简单, 但实际写起来有很多需要考虑的地方. 有两种解法, 分别是自定义方法和使用队列(还可以使用语言自带的方法, 这里不演示了).

解题的思路比较简单, 比较难的是代码实现中要考虑的内容, 所以代码中的注释比较多

自定义方法

由于步骤比较多, 所以建议分多个方法来实现. 首先去除字符串中的空格, 确保每个单词之间只有一个空格, 而字符串两端没有空格.

接下来将整个字符串反转, 然后再将每个单词反转即可.

队列

首先去除两侧字符, 建立一个队列和一个StringBuilder, 使用循环将单词添加到StringBuilder中, 若检测到空格则将StringBuilder中的内容push到队列里. 在循环结束后将StringBuilder中剩余的内容push到队列里. 最后返回时添加空格即可.

代码实现

自定义方法:

public class Solution {
    public static String reverseWords(String s) {
        // 去除空格
        StringBuilder sb = removeSpace(s);

        // 反转字符串
        reverse(sb, 0, sb.length() - 1);

        // 反转单词
        reverseWord(sb);

        return sb.toString();
    }

    private static void reverseWord(StringBuilder sb) {
        int length = sb.length();
        int start = 0, end = 0;
        while (start < length) {
            // 检测单词的末尾, 若检测到空格则说明当前单词已经结束
            while (end < length && sb.charAt(end) != ' ') {
                end++;
            }
            reverse(sb, start, end - 1);  // 因为end在空格位置上, 所以传入end - 1
            start = end + 1;  // 因为end在空格位置上, 所以下一个单词的开始应该为end + 1
            end++;
        }
    }
  
    private static void reverse(StringBuilder sb, int left, int right) {
        // 交换两侧字符位置
        while (left < right) {
            char temp = sb.charAt(left);
            sb.setCharAt(left++, sb.charAt(right));
            sb.setCharAt(right--, temp);
        }
    }

    private static StringBuilder removeSpace(String s) {
        int left = 0, right = s.length() - 1;
        // 去除开头的空格
        while (left <= right && s.charAt(left) == ' ') {
            ++left;
        }
        // 去除末尾的空格
        while (left <= right && s.charAt(right) == ' ') {
            --right;
        }
        StringBuilder stringBuilder = new StringBuilder();
        // 去除单词之间的空格
        while (left <= right) {
            char c = s.charAt(left);
            if (c != ' ') { // 若不为空格则将字符添加到stringBuilder
                stringBuilder.append(c);
            } else if(stringBuilder.charAt(stringBuilder.length() - 1) != ' ') {    // 若StringBuilder的最后一位不是空格则表示当前单词还没有空格分隔, 所以添加一个空格
                stringBuilder.append(c);
            }
            ++left;
        }
        return stringBuilder;
    }
}

队列:

public class Solution {
    public String reverseWords(String s) {
        int left = 0, right = s.length() - 1;
        // 去除左侧空格
        while (left <= right && s.charAt(left) == ' ') {
            left++;
        }
        // 去除右侧空格
        while (left < right && s.charAt(right) == ' ') {
            right--;
        }

        Deque<String> deque = new ArrayDeque<>();
        StringBuilder sb = new StringBuilder();

        while (left <= right) {
            char c = s.charAt(left);
            if ((sb.length() != 0) && (c == ' ')) {  // 若StringBuilder中有字符, 且当前字符为空格
                deque.offerFirst(sb.toString());  // 将StringBuilder中的内容添加到队列中
                sb.setLength(0);  // 将StringBuilder中的内容清空
            } else if (c != ' ') {
                sb.append(c);  // 添加字符
            }
            left++;
        }
        deque.offerFirst(sb.toString());  // 将StringBuilder中剩余的内容添加到队列
        return String.join(" ", deque);  // 从队列中取出单词, 并在它们直接使用空格分隔
    }
}