反转字符串中的单词 | LeetCode-151 | 字符串 | 6种写法

二分查找你学废了吗？快来看看这道题如何使用二分查找解决吧!

---

LeetCode链接：151. 反转字符串中的单词

---

1.题目描述

给你一个字符串 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 <= 10^4$
• s 包含英文大小写字母、数字和空格 ' '
• s 中 至少存在一个 单词

2.题解

• 思路：

  • 步骤1：去除字符串两端的空格
  • 步骤2：反转字符串
  • 步骤3：反转单词

• 方法1使用内置函数

• 方法2三个步骤的内置函数均是单独写的

• 方法3步骤2和步骤3可以通过双指针合并

2.1 内置函数

2.1.1 写法1

class Solution {
    public String reverseWords(String s) {
        // 去除字符串首尾的多余空格
        s = s.trim();
        
        // 通过正则表达式 "\\s+" 将字符串按照一个或多个空格进行分割，形成单词列表
        List<String> wordList = Arrays.asList(s.split("\\s+"));
        
        // 反转单词列表中的元素顺序
        Collections.reverse(wordList);
        
        // 将反转后的单词列表重新拼接成一个字符串，中间用单个空格隔开
        return String.join(" ", wordList);
    }
}

2.1.2 写法2

class Solution {
    public String reverseWords(String s) {
        // 按照空格分割字符串，生成单词数组
        String[] words = s.split(" +");
        // 使用 StringBuilder 高效地拼接字符串
        StringBuilder sb = new StringBuilder();
        // 从后向前遍历单词数组
        for (int i = words.length - 1; i >= 0; i--) {
            // 跳过空字符串
            if (words[i].isEmpty()) continue;
            
            // 拼接单词并加上空格
            sb.append(words[i]).append(" ");
        }
        // 去掉末尾的多余空格并返回结果
        return sb.toString().trim();
    }
}

2.1.3 写法3

class Solution {
    public String reverseWords(String s) {
        return Arrays.stream(s.trim().split(" +"))
                     .filter(word -> !word.isEmpty())
                     .collect(Collectors.joining(" ", "", ""));
    }
}

• 解释：

1. s.trim():
   • 去除字符串首尾的空格。
2. split(" +"):
   • 按照一个或多个空格分割字符串，生成单词数组。
3. stream():
   • 将单词数组转换为流。
4. filter(word -> !word.isEmpty()):
   • 过滤掉可能的空字符串元素。
5. collect(Collectors.joining(" ", "", "")):
   • 使用 Collectors.joining 将流中的单词连接成一个字符串，以空格分隔。

2.2 自行编写对应的函数

class Solution {
    public String reverseWords(String s) {
        // 去除多余的空格并返回字符数组
        char[] chs = trimSpaces(s);

        // 反转整个字符数组
        reverse(chs, 0, chs.length - 1);

        // 反转每个单词
        reverseEachWord(chs);

        // 将字符数组转换回字符串并返回
        return new String(chs);
    }

    public char[] trimSpaces(String s) {
        // 使用 StringBuilder 存储非空字符
        StringBuilder sb = new StringBuilder();
        int left = 0, right = s.length() - 1;

        // 找到首尾非空字符的位置
        while (left <= right && s.charAt(left) == ' ') left++;
        while (left <= right && s.charAt(right) == ' ') right--;

        // 记录非空字符并处理多余的空格
        while (left <= right) {
            char c = s.charAt(left);
            // 只在非空或前一个字符不是空格时添加字符
            if (c != ' ' || (sb.length() > 0 && sb.charAt(sb.length() - 1) != ' ')) {
                sb.append(c);
            }
            left++;
        }

        // 返回处理后的字符数组
        return sb.toString().toCharArray();
    }

    public void reverse(char[] chs, int begin, int end) {
        // 反转字符数组中的字符
        while (begin < end) {
            // 交换 begin 和 end 的字符
            char temp = chs[end];
            chs[end--] = chs[begin];
            chs[begin++] = temp;
        }
    }

    public void reverseEachWord(char[] chs) {
        int start = 0, end = 0;
        // 遍历字符数组
        while (start < chs.length) {
            // 找到单词的结束位置
            while (end < chs.length && chs[end] != ' ') end++;
            // 反转当前单词
            reverse(chs, start, end - 1);
            // 更新 start，准备查找下一个单词
            start = end + 1;
            end++;
        }
    }
}

2.3 双指针

2.3.1 写法1-自己写函数

class Solution {
    public String reverseWords(String s) {
        // 步骤1: 去除多余的空格
        s = trimSpaces(s);
        // 创建一个 StringBuilder 用于存储结果
        StringBuilder sb = new StringBuilder();
        int end = s.length(); // 字符串末尾的索引
        int begin = end - 1;  // 从最后一个字符开始

        // 使用双指针从后向前遍历字符串
        while (begin >= 0) {
            // 找到单词的开始位置
            while (begin >= 0 && s.charAt(begin) != ' ') begin--; // 遇到空格退出循环
            // 获取子串并添加到结果中
            sb.append(s.substring(begin + 1, end));
            // 如果不是最后一个单词，添加空格
            if (begin > 0) sb.append(' '); 
            // 更新 end 和 begin 以继续查找下一个单词
            end = begin; // 更新 end 为当前单词的开始位置
            begin--;     // 移动到下一个字符
        }
        
        // 返回最终结果
        return sb.toString();
    }

    public String trimSpaces(String s) {
        StringBuilder sb = new StringBuilder();
        int left = 0, right = s.length() - 1;
        // 找到首尾非空字符的位置
        while (left <= right && s.charAt(left) == ' ') left++;
        while (left <= right && s.charAt(right) == ' ') right--;
        // 记录非空字符并处理多余的空格
        while (left <= right) {
            char c = s.charAt(left);
            // 只在非空或前一个字符不是空格时添加字符
            if (c != ' ' || (sb.length() > 0 && sb.charAt(sb.length() - 1) != ' ')) {
                sb.append(c);
            }
            left++;
        }
        // 返回处理后的字符串
        return sb.toString();
    }
}

2.3.2 写法2-内置函数

class Solution {
    public String reverseWords(String s) {
        // 步骤1: 去除首尾空格
        s = s.trim();
        
        // 创建 StringBuilder 用于构建结果字符串
        StringBuilder sb = new StringBuilder();
        int end = s.length() - 1; // 记录字符串的末尾索引
        int begin = end; // 从末尾开始查找单词

        // 使用双指针从后向前遍历字符串
        while (begin >= 0) {
            // 找到当前单词的开始位置
            while (begin >= 0 && s.charAt(begin) != ' ') begin--; // 遇到空格退出循环
            // 获取当前单词并添加到结果中
            sb.append(s.substring(begin + 1, end + 1));
            // 如果不是最后一个单词，则在单词后添加空格
            if (begin > 0) sb.append(' '); 
            // 跳过空格，更新 begin 以找到下一个单词
            while (begin >= 0 && s.charAt(begin) == ' ') begin--; // 遇到字母退出循环
            // 更新 end 为当前单词的开始位置
            end = begin;
        }

        // 返回最终构建的字符串
        return sb.toString();
    }
}