151 翻转字符串里的单词

题目

给定一个字符串，逐个翻转字符串中的每个单词。

说明：

无空格字符构成一个 单词 。 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

示例 1：

输入："the sky is blue"
输出："blue is sky the"
``
示例 2：

```js
输入："  hello world!  "
输出："world! hello"
解释：输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：

输入："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 <= 104 s 包含英文大小写字母、数字和空格 ' ' s 中 至少存在一个 单词

进阶：

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

题解

1. 使用 match 匹配单词组成的数组，使用 reverse + join 来获取翻转后的字符串

TIP

执行用时：84 ms, 在所有 JavaScript 提交中击败了 56.59% 的用户
内存消耗：38.8 MB, 在所有 JavaScript 提交中击败了 32.65% 的用户

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
    let strList = s.match(/\S+/gi)
    return strList.reverse().join(' ')
};

• 时间复杂度： `O(n)`，使用 match 方法进行查找
• 空间复杂度： `O(n)`，使用了额外空间用来保存拆分后的数组
• 最好情况： 传入的字符串较短，则进行较少操作
• 最坏情况： 传入的字符串较长，则需要进行多次操作

2. 使用队列来储存匹配到的单词

TIP

执行用时：92 ms, 在所有 JavaScript 提交中击败了 29.52% 的用户
内存消耗：39.2 MB, 在所有 JavaScript 提交中击败了 22.91% 的用户

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
    let left = 0
    let right = s.length - 1
    let word = '' // 单词
    let queue = [] // 储存匹配到的单词
    while(s[left] == ' ') left++ // 排除字符串左侧的空白
    while(s[right] == ' ') right-- // 排除字符串右侧的空白 

    while(left <= right) {
        let str = s[left]
        if(str == ' ' && word) {
            queue.unshift(word)
            word = ''
        } else if(str != ' '){
            word += str
        }
        left++
    }
    queue.unshift(word)
    return queue.join(' ')
};

• 时间复杂度： `O(n)`，使用 while 循环来进行查找。
• 空间复杂度： `O(n)`，使用了一个数组来储存单词。
• 最好情况： 传入的字符串较短，则进行较少操作
• 最坏情况： 传入的字符串较长，则需要进行多次操作