题目

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

 示例 4：
输入：s = "  Bob    Loves  Alice   "
输出："Alice Loves Bob"

 示例 5：
输入：s = "Alice does not even like bob"
输出："bob like even not does Alice"

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

 进阶： 
 请尝试使用 O(1) 额外空间复杂度的原地解法。 

方法

直接调方法

\s+是匹配所有显示空格的类型，包括：

• \f -> 匹配一个换页

• \n -> 匹配一个换行符

• \r -> 匹配一个回车符

• \t -> 匹配一个制表符

• \v -> 匹配一个垂直制表符

• 时间复杂度：O(n)

• 空间复杂度：O(n)

class Solution {
    public String reverseWords(String s) {
        s = s.trim(); //去除两头的空格
        List<String> arr = Arrays.asList(s.split("\\s+"));
        Collections.reverse(arr);
        return String.join(" ",arr);
    }
}

双端队列法

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

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> queue = new LinkedList<>();
        StringBuffer word = new StringBuffer();
        while (left<=right){
            char c  = s.charAt(left);
            if(word.length()>0&&c==' '){
                queue.offerFirst(word.toString());
                word.setLength(0);
            }else if(c!=' '){
                word.append(c);
            }
            left ++;
        }
        queue.offerFirst(word.toString());
        return String.join(" ",queue);
    }
}

二次翻转法

先去除两端的空格，然后翻转字符串，然后再翻转字母

• 时间复杂度：O(n)
• 空间复杂度：O(1)