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) 额外空间复杂度的原地解法。

解题思路

我的思路：

设定可变长字符串 sb 来记录目标字符串
从后往前遍历初始字符串
未到初始字符串头部，碰到单词尾部的空格就跳过
未到初始字符串头部，碰到非空格字符就开始记录单词 word
反转单词 word，并将其加入目标字符串 sb
未到初始字符串头部，碰到单词头部的空格就跳过
如果没有到达原始字符串的开头，就往目标字符串里加空格，否则就不加空格
遍历结束时，返回目标字符串 sb

我的代码

java

public String reverseWords(String s) {
    StringBuilder sb = new StringBuilder();
    int i = s.length() - 1;
    while (i >= 0) {
        // 用于存储反转后的单词
        StringBuilder word = new StringBuilder();
       // 跳过尾部的空格字符
        while (i >= 0 && s.charAt(i) == ' ') {
            i--;
        }
        // 从后向前遍历字符串，提取单词
        while (i >= 0 && s.charAt(i) != ' ') {
            word.append(s.charAt(i));
            i--;
        }
        // 反转提取到的单词
        reverseString(word, 0, word.length() - 1);
        // 将反转后的单词添加到结果中
        sb.append(word);
        // 跳过单词间的空格字符
        while (i >= 0 && s.charAt(i) == ' ') {
            i--;
        }
        // 在结果单词间添加一个空格（如果不是最后一个单词）
        if (i >= 0) {
            sb.append(' ');
        }
    }
    return sb.toString();
}

// 反转StringBuilder中指定区间[start, end]的字符
public void reverseString(StringBuilder sb, int start, int end) {
    while (start < end) {
        char temp = sb.charAt(start);
        sb.setCharAt(start, sb.charAt(end));
        sb.setCharAt(end, temp);
        start++;
        end--;
    }
}

时间复杂度: O(n)

空间复杂度: O(n)

双指针法

上述实现中，每个单词被逐个字符逆序添加到 word 中，然后整个 word 被反转回来，但其实可以直接以正确的顺序添加字符到 word 中来减少字符串的反转操作。

此外，可以在添加每个单词到 sb 之前检查是否需要添加空格，从而减少对空格的处理。

思路详解

倒序遍历字符串 s
设定指针 left、right 来记录当前单词的左右边界下标
每确定一个单词的边界，就将其添加至单词列表 sb
最终，将单词列表拼接为字符串并返回

代码展示

java

public String reverseWords(String s) {
    StringBuilder sb = new StringBuilder();
    int right = s.length() - 1;
    while (right >= 0) {
        if (s.charAt(right) == ' ') { // 跳过空格字符
            right--;
        } else if (s.charAt(right) != ' ') {
            int left = right;
            // 查找单词的开始位置
            while (left >= 0 && s.charAt(left) != ' ') {
                left--;
            }    
            // 添加一个空格（除非是第一个单词）
            if (sb.length() > 0) {
                sb.append(' ');
            }
            // 添加单词,左闭右开
            // sb.append(s.substring(j + 1, i + 1));
            sb.append(s, left + 1, right + 1);
            // 开始找下一个单词 此时right刚好是下一单词的left
            right = left;
        }
    }
    return sb.toString();
}

时间复杂度: O(n)

空间复杂度: O(n)

总结

这道题目可以说是综合考察了字符串的多种操作。

151.反转字符串中的单词 ​

解题思路 ​

我的代码 ​

双指针法 ​

思路详解 ​

代码展示 ​

总结 ​