翻转单词顺序

[Bulandent]

翻转单词顺序

难度：简单
来源：剑指 Offer 58 - I

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串 "I am a student. "，则输出 "student. a am I"。

示例 1：

输入: "the sky is blue"
输出: "blue is sky the"

示例 2：

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

示例 3：

输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

题解一：分割+倒序

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
    return s
        .trim()        // 去除首尾空格
        .split(/\s+/)  // 按照空格（可能是多个）分组
        .reverse()     // 反转数组
        .join(' ')     // 合并成字符串
};

• 时间复杂度：，执行用时：80 ms
• 空间复杂度：，内存消耗：38.9MB

题解二：双指针

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
    s = s.trim()  // 去除字符串左右两边空格
    let res = []
    let j = s.length - 1, i = j  // i、j分别记录单词左右边界
    while(i >= 0) {  // 倒序遍历字符串s
        while(i >= 0 && s.charAt(i) !== ' ') i--  // 确定一个单词的左边界
        res.push(s.substring( i + 1, j + 1 ) + ' ')  // 在单词后面拼一个空格，并加入到返回结果的数组中
        while(i >= 0 && s.charAt(i) === ' ') i--  // 把指针移动到下一个单词的右边界
        j = i
    }
    return res.join('').trim()
}

• 时间复杂度：，执行用时：84 ms
• 空间复杂度：，内存消耗：39.6 MB