Leetcode 151.翻转字符串里的单词（画图分析）

力扣传送门(opens new window)

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

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

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

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

解题思路：

代码实现：

class Solution {
    public String reverseWords(String s) {
        if(s == null || s.length() == 0){
            return s;
        }
        //1.去掉多余的空格
        StringBuilder sb = removeSpace(s);
        //2.反转整个字符串
        reverseString(sb, 0, sb.length() - 1);
        //3.反转单个单词
        reverseEachWord(sb);
        return sb.toString();
    }

    // 反转每个单词
    public void reverseEachWord(StringBuilder sb) {
        int left = 0;
        int right = 1;
        while(right < sb.length()) {
            // 找到单词的末尾
            while(right < sb.length() && sb.charAt(right) != ' ') {
                right++;
            }
            // 反转单词
            reverseString(sb, left, right - 1);
            left = right + 1;
            right = left + 1;
        }
    }

    // 反转字符串的指定部分
    public void reverseString(StringBuilder sb, int left, int right) {
        while(left < right) {
            char temp = sb.charAt(left);
            sb.setCharAt(left, sb.charAt(right));
            sb.setCharAt(right, temp);
            left++;
            right--;
        }
    }

    // 去除字符串两端多余的空格
    public StringBuilder removeSpace(String s) {
        int left = 0;
        int right = s.length() - 1;
        StringBuilder sb = new StringBuilder();
        while(s.charAt(left) == ' ') {
            left++;
        }
        while(s.charAt(right) == ' ') {
            right--;
        }
        while(left <= right) {
            // 如果当前字符不是空格，或者前一个字符不是空格，则将该字符添加到StringBuilder中
            if(s.charAt(left) != ' ' || sb.charAt(sb.length() - 1) != ' ') {
                sb.append(s.charAt(left));
            }
            left++;
        }
        return sb;
    }
}

解释下这三行代码：

            // 反转单词
            reverseString(sb, left, right - 1);
            left = right + 1;
            right = left + 1;

在方法 reverseEachWord中，这里的 right - 1是为了排除空格符号，只反转单词字符而不包括空格。

假设我们有一个字符串："Hello World"，并假设我们已经去掉了多余的空格，现在需要反转每个单词。我们使用两个指针 left和 right来标记每个单词的起始和结束位置。

初始时，left指向单词的第一个字符，right指向 left的下一个位置。我们向右移动 right，直到遇到空格或到达字符串的末尾。此时，right指向的位置就是当前单词的末尾字符的下一个位置。

为了反转当前单词，我们调用 reverseString(sb, left, right - 1)。传递 right - 1是因为 right指向的位置是下一个单词的起始位置或字符串的末尾，我们需要将反转的范围限制在当前单词内，不包括下一个单词的起始位置或字符串的末尾。

然后，我们更新 left和 right的位置，将 left设置为当前单词的下一个位置（即 right + 1），将 right设置为 left的下一个位置（即 left + 1），以便处理下一个单词。

这样，通过每次反转一个单词，我们可以逐步完成整个字符串的单词反转操作。