📃 题目描述

题目链接：151. 翻转字符串里的单词 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

给你一个字符串 s ，逐个翻转字符串中的所有 单词 。

单词 是由非空格字符组成的字符串。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"
解释：如果两个单词间有多余的空格，将翻转后单词间的空格减少到只含一个。

提示：

• s 包含英文大小写字母、数字和空格 ' '

🔔 解题思路

本题的解题思路很简单：

1. 移除多余空格
2. 先反转整个字符串
3. 再逐个反转每个单词（就是这道题目：557. 反转字符串中的单词 III - 力扣（LeetCode） (leetcode-cn.com) (opens new window) ）

除了第一步我们没做过，后两步我们都已经知道该怎么做了。

我们来看看如何移除多余的空格，使用一个额外的空间 StringBuilder 存储移除多余的空格后的字符串，也是分三步，使用两个指针，一个指针 start 指向字符串开头，一个指针 end 指向字符串结尾，这两个指针的主要目的是用来跳过首尾的空格的，帮助我们定位处理中间多余空格的起始和结束位置：

1. 去除开头多余的空格（start ++）
2. 去除末尾多余的空格（end --）
3. 去除中间多余的空格（基本思路就是如果是连续空格的话, 我们只往 StringBuilder 中加入第一个空格)

class Solution {
    public String reverseWords(String s) {
        // 去除首尾以及中间多余的空格
        StringBuilder sb = removeExtraSpace(s);
        // 反转整个字符串
        reverse(sb, 0, sb.length() - 1);
        // 挨个反转每个单词
        reverseWordsByEach(sb);
        return sb.toString();

    }

    /**
     * 去除首尾以及中间多余的空格
     */
    private StringBuilder removeExtraSpace(String s) {
        int start = 0;
        int end = s.length() - 1;
        // 去除开头多余的空格
        while (s.charAt(start) == ' ') {
            start ++;
        }
        // 去除末尾多余的空格
        while (s.charAt(end) == ' ') {
            end --;
        }

        // 去除中间多余的空格
        StringBuilder sb = new StringBuilder();
        while (start <= end) {
            char c = s.charAt(start);
            // 不是空格的字符肯定是要加入 sb 的
            // 还有,如果不是连续空格,也需要加入(或者说, 如果是连续空格, 我们只加入第一个空格)
            if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
                sb.append(c);
            }
            start ++;
        }

        return sb;
    }

    /**
     * 逐个反转每个单词
     */
    private void reverseWordsByEach(StringBuilder sb) {
        if (sb == null || sb.length() == 0 || sb.equals(" ")) {
            return ;
        }

        int start = 0;
        int end = 0;
        while (end < sb.length()) {
            // 找到单词的结束位置（最后一个字符的位置）
            while (end < sb.length() - 1 && sb.charAt(end + 1) != ' ') {
                end ++;
            }

            // 反转这个单词
            reverse(sb, start, end);

            // 继续寻找下一个单词
            end = end + 2;
            start = end;
        }
    }

    /**
     * 反转从 left 到 right 位置的字符串
     */
    private 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);
            left ++;
            right --;
        }
    }
}

💥 复杂度分析

• 空间复杂度：O(N)
• 时间复杂度：本题总共三个串行的步骤，每个步骤的时间复杂度都是 O(N)，所以总的时间复杂度是 O(N)