151. 反转字符串中的单词

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

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

调用Collections.reverse

trim+split+正则表达式+Collections.reverse+join

class Solution {
    public String reverseWords(String s) {
        // 除去开头和末尾的空白字符
        s = s.trim();
        
        // 正则匹配连续的空白字符作为分隔符分割
        // "\\s+" 匹配一个或多个空白字符，split 方法将字符串按空白字符分割成单词列表
        List<String> wordList = Arrays.asList(s.split("\\s+"));
        
        // 反转单词列表。将单词列表 wordList 中的元素顺序反转
        Collections.reverse(wordList);
        
        // 使用空格将单词列表拼接成一个字符串
        // String.join(" ", wordList) 将列表中的单词用空格连接成一个字符串
        return String.join(" ", wordList);
    }
}

• 时间复杂度： $O(n)$ ，其中 $n$ 为输入字符串的长度。
• 空间复杂度： $O(n)$ ，用来存储字符串分割之后的结果。

倒序遍历+StringBuilder

class Solution {
    public String reverseWords(String s) {
        String[] strs = s.trim().split(" ");        // trim删除首尾空格，split分割字符串
        StringBuilder res = new StringBuilder();
        for (int i = strs.length - 1; i >= 0; i--) { // 倒序遍历单词列表
            // 遇到空单词则跳过。split(" ") 方法在处理连续多个空格时会生成空字符串，
            // 例如Hello  world（注意里面有两个空格），split后得到strs = ["Hello", "", "world"]
            if (strs[i].equals("")) continue;        
            res.append(strs[i] + " ");              // 将非空单词拼接至 StringBuilder
        }
        return res.toString().trim();               // 转化为字符串，删除尾部空格，并返回
    }
}

class Solution {
    public String reverseWords(String s) {
        // trim删除首尾空格，split分割字符串。注意split("//s+")生成的字符串数组中没有空字符串
        String[] strs = s.trim().split("\\s+");        
        StringBuilder res = new StringBuilder();
        for (int i = strs.length - 1; i >= 0; i--) { // 倒序遍历单词列表
            res.append(strs[i] + " ");              // 将非空单词拼接至 StringBuilder
        }
        return res.toString().trim();               // 转化为字符串，删除尾部空格，并返回
    }
}

时间复杂度O(N)，空间复杂度O(N)。

• split() 方法： 为 O(N)。

• trim() 和 strip() 方法： 最差情况下（当字符串全为空格时），为 O(N)。

• join() 方法： 为 O(N)。

• reverse() 方法： 为 O(N)。

• split(" ")：使用单个空格作为分隔符，连续的空格会导致产生空字符串。

• split("\\s+")：使用一个或多个空白字符作为分隔符，连续的空白字符不会导致产生空字符串。例如“Hello world”（注意里面有两个空格）， split("\\s+")后得到 strs = ["Hello", "world"]