151. 反转字符串中的单词

✨核心逻辑

本题要求反转字符串中单词的顺序，并处理多余的空格。这里提供两种思路：

API 思路（推荐实际开发使用）：直接使用 Java 提供的字符串处理方法。先用 trim() 去除首尾空格，再用正则 split("\\s+") 按一个或多个空格将字符串切分为单词数组。最后倒序遍历数组，并用空格拼接即可。

🔥代码实现（含详细变量注释）

package array_string;

import java.util.ArrayDeque;
import java.util.Deque;

public class reverseWords_151 {
    
    // 思路 1：API 思路（利用 split 和 trim 快速实现）
    public String reverseWords1(String s) {
        // sb：用于动态构建最终返回的结果字符串
        StringBuilder sb = new StringBuilder();
        
        // split：先使用 trim() 去除字符串首尾的空格，再用 split("\\s+") 按照一个或多个空格切分出所有单词
        String[] split = s.trim().split("\\s+");
        
        // i：遍历指针，从数组的最后一位（即原字符串的最后一个单词）开始，倒序遍历到 0
        for (int i = split.length - 1; i >= 0; i--) {
            // 如果不是最后一个单词（即在单词之间），则添加单词 + 一个空格
            if (i != 0) {
                sb.append(split[i] + " ");
            } else {
                // 如果是最后一个需要拼接到最前面的单词，后面无需加空格
                sb.append(split[i]);
            }
        }
        // 返回构建好的反转字符串
        return sb.toString();
    }

⏱️复杂度分析-----思路 1（API 方法)
- 时间复杂度：O(N)，其中 N 是字符串的长度。split 和反转拼接操作都需要线性时间遍历字符串。
- 空间复杂度：O(N)，主要消耗在于 split 方法切分出来的单词数组，以及 StringBuilder 占用的空间。

双端队列思路（底层原理）：不依赖 API，手动遍历字符串。使用一个 StringBuilder 临时收集单词字符，每当遇到空格且单词不为空时，将单词从头部插入到双端队列 Deque 中。最后从头部依次弹出并拼接，即可实现反转效果。


    // 思路 2：双端队列思路（底层手动解析空格，适合要求手动实现的场景）
    public String reverseWords2(String s) {
        // deque：使用双端队列，由于要从头部插入（addFirst），天然的倒序存储特性非常适合做反转
        Deque<String> deque = new ArrayDeque<>();
        // s1：用于在遍历过程中，临时收集当前正在解析的单个单词的字符
        StringBuilder s1 = new StringBuilder();

        // 1. 遍历输入字符串的每一个字符
        for (int i = 0; i < s.length(); i++) {
            // c：当前索引 i 对应的字符
            char c = s.charAt(i);

            // 如果字符不是空格，说明它是单词的一部分，拼接到 s1 中
            if (c != ' ') {
                s1.append(c);
            } else {
                // 如果遇到空格，且 s1 中已经有收集好的单词（长度大于 0）
                if (s1.length() > 0) {
                    // 将该单词转换为 String，插入到双端队列的头部（反转顺序）
                    deque.addFirst(s1.toString());
                    // 清空 s1，准备收集下一个单词
                    s1.setLength(0);
                }
            }
        }
        
        // 2. 循环结束后，如果 s1 中还有剩余未入队的单词，也要入队
        if (s1.length() > 0) {
            deque.addFirst(s1.toString());
            s1.setLength(0);
        }
        
        // 3. 出队拼接得到最终结果
        while (!deque.isEmpty()) {
            // 从双端队列头部依次弹出单词，追加到 s1 中
            s1.append(deque.removeFirst());
            // 如果队列中还有元素，则需要在当前单词后面添加一个空格分隔
            if (!deque.isEmpty()) {
                s1.append(" ");
            }
        }
        // 返回拼好的反转结果字符串
        return s1.toString();
    }
}