151.翻转字符串里的单词（字符串算法）

151.翻转字符串里的单词

力扣题目链接(opens new window)

给你一个字符串 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 中 至少存在一个 单词

思路

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

一些同学会使用split库函数，分隔单词，然后定义一个新的string字符串，最后再把单词倒序相加，那么这道题题目就是一道水题了，失去了它的意义。

所以这里我还是提高一下本题的难度：不要使用辅助空间，空间复杂度要求为O(1)。

不能使用辅助空间之后，那么只能在原字符串上下功夫了。

想一下，我们将整个字符串都反转过来，那么单词的顺序指定是倒序了，只不过单词本身也倒序了，那么再把单词反转一下，单词不就正过来了。

所以解题思路如下：

• 移除多余空格
• 将整个字符串反转
• 将每个单词反转

举个例子，源字符串为："the sky is blue "

• 移除多余空格 : "the sky is blue"
• 字符串反转："eulb si yks eht"
• 单词反转："blue is sky the"

这样我们就完成了翻转字符串里的单词。

class Solution {public String reverseWords(String s) {// 1. 去除多余空格StringBuilder sb = removeSpace(s);// 2. 反转整个字符串reverseString(sb, 0, sb.length() - 1);// 3. 反转每一个单词reverseEachWord(sb);  // ✅ 改成 reverseEachWord，不是 reverseWordsreturn sb.toString();}// 去除多余空格private StringBuilder removeSpace(String s) {int start = 0;int end = s.length() - 1;// 跳过开头空格while (start <= end && s.charAt(start) == ' ') start++;// 跳过结尾空格while (start <= end && s.charAt(end) == ' ') end--;StringBuilder sb = new StringBuilder();while (start <= end) {char c = s.charAt(start);// 只有当前字符不是空格，或者上一个字符不是空格时才添加（避免连续空格）if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {sb.append(c);}start++;}return sb;}// 反转 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--;}}// 反转每一个单词private void reverseEachWord(StringBuilder sb) {int start = 0;int end = 1;int n = sb.length();while (start < n) {while (end < n && sb.charAt(end) != ' ') {end++;}reverseString(sb, start, end - 1);  // 反转当前单词start = end + 1;  // 移到下一个单词开头end = start + 1;  // end 在 start 后一位}}
}

/解法二：创建新字符数组填充。时间复杂度O(n)
class Solution {public String reverseWords(String s) {//源字符数组char[] initialArr = s.toCharArray();//新字符数组char[] newArr = new char[initialArr.length+1];//下面循环添加"单词 "，最终末尾的空格不会返回int newArrPos = 0;//i来进行整体对源字符数组从后往前遍历int i = initialArr.length-1;while(i>=0){while(i>=0 && initialArr[i] == ' '){i--;}  //跳过空格//此时i位置是边界或!=空格，先记录当前索引，之后的while用来确定单词的首字母的位置int right = i;while(i>=0 && initialArr[i] != ' '){i--;} //指定区间单词取出(由于i为首字母的前一位，所以这里+1,)，取出的每组末尾都带有一个空格for (int j = i+1; j <= right; j++) {newArr[newArrPos++] = initialArr[j];if(j == right){newArr[newArrPos++] = ' ';//空格}}}//若是原始字符串没有单词，直接返回空字符串；若是有单词，返回0-末尾空格索引前范围的字符数组(转成String返回)if(newArrPos == 0){return "";}else{return new String(newArr,0,newArrPos-1);}}
}

// 解法二：创建新字符数组填充。时间复杂度O(n)

注释说明：这是第二种解法，通过新建一个字符数组来按顺序填充翻转后的单词。

• 时间复杂度为 O(n)，n 是字符串长度；
• 核心思想是从后往前扫描原字符串，把每个单词正序地放入新数组中，并在后面加空格分隔。

class Solution {

定义名为 Solution 的类，用于封装解题方法（常见于 LeetCode 风格）。

    public String reverseWords(String s) {

定义公共方法 reverseWords，接收一个字符串 s，返回类型为 String，功能是将字符串中单词顺序反转。

        // 源字符数组char[] initialArr = s.toCharArray();

将输入字符串 s 转换为字符数组 initialArr，便于逐个访问和判断字符。

• toCharArray() 是 Java 内置方法，将字符串转为 char[]。

        // 新字符数组char[] newArr = new char[initialArr.length + 1];

创建一个新的字符数组 newArr，长度比原数组多 1。

• 原因：后续逻辑中，每写入一个单词后会追加一个空格 ' '，可能导致多一个空格；
• 多出的 +1 是为了防止索引越界（虽然实际使用不会超过原长 +1）；
• 最终返回时会去掉末尾多余空格。

        int newArrPos = 0;

newArrPos 是新数组的写入指针，表示当前要写入的位置索引，初始为 0。

        // i 来进行整体对源字符数组从后往前遍历int i = initialArr.length - 1;

设置指针 i，从原字符数组的最后一个位置开始，从右向左遍历整个字符串。

        while (i >= 0) {

外层循环：只要 i 没越界（即未处理完所有字符），就继续处理。

            while (i >= 0 && initialArr[i] == ' ') { i--; }

跳过末尾或单词之间的连续空格。

• 这个循环结束后，i 要么指向一个非空格字符（单词的一部分），要么是 -1（已到开头）。

            // 此时 i 位置是边界或 != 空格，先记录当前索引，// 之后的 while 用来确定单词的首字母的位置int right = i;

记录当前单词的右边界索引（即单词最后一个字符的位置）。

• 因为我们是从右往左扫描，所以先遇到的是单词的结尾。

            while (i >= 0 && initialArr[i] != ' ') { i--; }

继续向前移动 i，直到遇到空格或到达字符串开头。

• 这个循环结束后，i 指向当前单词前面的第一个空格，或者 -1；
• 所以当前单词的范围是 [i+1, right]。

            // 指定区间单词取出（由于 i 为首字母的前一位，所以这里 +1）// 取出的每组末尾都带有一个空格for (int j = i + 1; j <= right; j++) {newArr[newArrPos++] = initialArr[j];if (j == right) {newArr[newArrPos++] = ' '; // 添加空格}}

将当前单词从原数组中取出，并正序写入新数组：

• j 从 i+1 开始（单词首字母），到 right 结束（单词尾字母）；
• 每个字符依次写入 newArr，并移动 newArrPos；
• 当 j == right（最后一个字符）时，额外添加一个空格 ' ' 作为单词分隔符。

✅ 注意：这样会导致每个单词后面都加了一个空格，包括最后一个单词，所以我们最后要去掉末尾多余的那个空格。

        }

结束外层 while (i >= 0) 循环。

        // 若原始字符串没有单词，直接返回空字符串；// 若是有单词，返回 0 到末尾空格索引前范围的字符数组（转成 String 返回）if (newArrPos == 0) {return "";} else {return new String(newArr, 0, newArrPos - 1);}

处理最终结果：

• 如果 newArrPos == 0，说明没有写入任何内容 → 原字符串全是空格或为空 → 返回空字符串 ""；
• 否则，使用 new String(char[], offset, count) 构造函数：
  • 从 newArr 的索引 0 开始；
  • 取 newArrPos - 1 个字符；
  • 目的是去掉最后多加的那个空格。

🔍 举例：如果写入了 "blue is sky the "（最后有个空格），我们只取前 newArrPos-1 个字符，变成 "blue is sky the"。

    }

结束 reverseWords 方法。

}

结束 Solution 类。

---

✅ 算法流程图解（以 " hello world " 为例）

步骤	操作
原始字符串	" hello world "
转为数组	[' ',' ','h','e','l','l','o',' ',' ',' ','w','o','r','l','d',' ',' ']
从后往前扫描	先找到 'd'，再往前找单词边界
找到 "world" → 写入新数组	['w','o','r','l','d',' ']
继续找 "hello" → 写入	['w','o','r','l','d',' ','h','e','l','l','o',' ']
返回时去掉末尾空格	"world hello"

---

✅ 时间复杂度分析

• 每个字符最多被访问常数次（扫描两次：一次跳过空格，一次复制）；
• 总体时间复杂度：O(n)，n 是字符串长度。

✅ 空间复杂度分析

• 使用了两个字符数组：initialArr（n）和 newArr（n+1）；
• 空间复杂度：O(n)。