反转字符串中的单词

背景

• 数据结构–反转字符串中的单词

• 博主以代码随想录算法公开课进行学习

问题

给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：
输入: “the sky is blue”
输出: “blue is sky the”

示例 2：
输入: " hello world! "
输出: “world! hello”
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：
输入: “a good example”
输出: “example good a”
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个

思路

• 清理多余空格：去除字符串首尾的空格，同时将单词之间的多个空格缩减为一个。
• 反转整个字符串：将清理后的字符串整体反转。
• 反转每个单词：遍历反转后的字符串，将每个独立的单词再反转回来，最终得到单词顺序反转的结果。
• 快慢指针法：
  • 快指针（fast）：负责遍历原始字符数组，寻找有效字符（非空格）。
  • 慢指针（slow）：负责在原数组上 “构建” 无多余空格的新数组，记录有效字符的存放位置。

代码

class Solution {
    public String reverseWords(String s) {
         // 1. 去除多余空格（首尾空格 + 单词间多余空格）
        char[] chars = s.toCharArray();
        chars = reverseExtraSpaces(chars);
        
        // 2. 反转整个字符串
        reverse(chars,0,chars.length-1);
        
        // 3. 反转每个单词
        reverseEachWord(chars);
        return new String(chars);
    }
    
    //去掉多余空格
    public char[] reverseExtraSpaces(char[] chars){
        int slow = 0;// 慢指针：记录有效字符的位置
        for(int fast = 0;fast<chars.length;fast++){
             // 只处理非空格字符（跳过所有空格）
            if(chars[fast] != ' '){ 
             // 如果不是第一个单词，先在单词前加一个空格（避免开头有空格）   
                if(slow != 0){
                    chars[slow++] = ' '; 
                    }
                 // 把当前单词的所有字符复制到慢指针位置
                 // 循环条件：fast没越界 且 当前字符不是空格（即还在同一个单词内）
                    while(fast < chars.length && chars[fast] != ' ')
                       chars[slow++] = chars[fast++];
            }
        }
        // 截取有效长度的字符数组（去掉后面的无效部分）
        char[] newChars = new char[slow];
        System.arraycopy(chars,0,newChars,0,slow);
        return newChars;
    }
    //反转指定区间的字符串
    public void reverse(char[] chars, int left, int right){
        if(right>=chars.length){
            return;
        }
         // 双指针交换左右字符，向中间靠拢
        while(left<right){
            char temp = chars[left];
            chars[left] = chars[right];
            chars[right] = temp;
            left++;
            right--;
        }
    }
    //反转每个单词
    public void reverseEachWord(char[] chars){
        int start = 0;// 记录每个单词的起始位置
        for(int end = 0;end <=chars.length;end++){
            if(end == chars.length || chars[end] == ' '){
                reverse(chars,start,end-1);
                start = end + 1;// 更新下一个单词的起始位置
            }
        }
    }
}

总结

• 记住三步走：清理空格、反转整体、反转单词（区间）