【LeetCode】151. 反转字符串中的单词（中等）——代码随想录算法训练营Day08

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

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

文章讲解：代码随想录

视频讲解：字符串复杂操作拿捏了！ | LeetCode:151.翻转字符串里的单词_哔哩哔哩_bilibili

题解1：暴力法

思路：将字符串分割成单词数组，再反转数组，最后将数组转换成字符串。

此解法只供娱乐，起不到练习的效果。

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
    return s.split(/ +/).filter(s => s).reverse().join(" ");
};

分析：时间复杂度为 O(n)，空间复杂度为 O(n)。

题解2：快慢指针

思路：先将字符串整体翻转一遍，再将每个单词翻转一遍，就得到一个反转单词后的字符串，再使用双指针去除字符串的空格，即可得到答案。

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
    // 翻转整个字符串
    s = s.split("").reverse();

    // 翻转字符串数组中的单词
    let i = 0;
    while (i < s.length) {
        while (s[i] === " ") {
            i++;
        }
        let left = i, right = i + 1;
        while (right < s.length && s[right] !== " ") {
            right++;
        }
        i = right--;
        while (left < right) {
            const _ = s[left];
            s[left++] = s[right];
            s[right--] = _;
        }
    }

    // 去除多余的空格
    let slow = fast = 0;
    while (fast < s.length) {
        if (s[fast] !== " ") {
            slow > 0 && (s[slow++] = " ");
            while (fast < s.length && s[fast] !== " ") {
                s[slow++] = s[fast++];
            }
        }
        fast++;
    }
    return s.slice(0, slow).join("");
};

分析：时间复杂度为 O(n)，空间复杂度为 O(n)。

PS：同样的解法在 c、c++ 中空间复杂度是 O(1)，因为 c、c++ 可以在原字符串上修改。

收获

更加熟悉字符串的操作，对边界判定的掌控更加精确。