翻转字符串里的单词

## 1 题目

给你一个字符串 s ，逐个翻转字符串中的所有 单词 。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。

**说明：**

* 输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
* 翻转后单词间应当仅用一个空格分隔。
* 翻转后的字符串中不应包含额外的空格。

**示例 1：**

```txt
输入：s = "the sky is blue"
输出："blue is sky the"
```

**示例 2：**

```txt
输入：s = "  hello world  "
输出："world hello"
解释：输入字符串可以在前面或者后面包含多余的空格，但是翻转后的字符不能包括。
```

**示例 3：**

```txt
输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，将翻转后单词间的空格减少到只含一个。
```

**示例 4：**

```txt
输入：s = "  Bob    Loves  Alice   "
输出："Alice Loves Bob"
```

**示例 5：**

```txt
输入：s = "Alice does not even like bob"
输出："bob like even not does Alice"
```

**提示：**

* 1 <= s.length <= 104
* s 包含英文大小写字母、数字和空格 ' '
* s 中 至少存在一个 单词

**进阶：**

* 请尝试使用 O(1) 额外空间复杂度的原地解法。

## 2 解题思路

### 2.1 解法一：栈

#### 2.1.1 问题分析

1. 该方法的基本思想是依次遍历字符串中的字符，然后截取每个单词，并将截取后的单词放到栈中。
2. 字符串遍历结束后，再依次遍历栈中的元素，并用 StringBuffer 以空格为分隔符将这些单词并接起来，最后直接返回即可。
   
   ![](/media/202107/151-翻转字符串里的单词（解法一：栈）_1625841088.gif)

#### 2.1.2 参考代码

```java
/**
 * 151. 翻转字符串里的单词（版本 1：栈）
 *
 * @param s 字符串
 * @return 翻转后的字符串
 */
public String reverseWordsV1(String s) {
    //  截取每个单词的起始位置
    int start = 0, end = 0;
    //  判断单词的位置是否开始计数
    boolean isBegin = false;
    //  存储截取后的单词
    Stack<String> stack = new Stack<>();
    //  用于将栈中的单词转化为字符串
    StringBuffer sb = new StringBuffer();

//  逐个遍历字符串中的每个字符，并截取相应的单词
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) != ' ') {
            //  当前字符不是空字符
            if (isBegin) {
                //  已经开始对当前单词的位置进行计数，将对应的下标加 1
                end++;
            } else {
                //  开始对当前单词的位置进行计数，使用 start 记录当前单词的起始位置
                start = i;
                //  使用 end 记录当前单词的结束位置，其中 end 会一直累加，直到遇到空字符
                end = start + 1;
                //  标记开始对当前单词的位置进行计数
                isBegin = true;
            }
        } else {
            //  当前字符是空字符
            if (isBegin) {
                //  已经开始对当前单词的位置进行计数，现在遇到了空字符，因此需要停止对当前单词的位置进行计数，然后截取字符串中 [start, end) 之间的字符，这些字符便构成了当前单词
                stack.push(s.substring(start, end));
                //  标记停止对当前单词的位置进行计数
                isBegin = false;
            }
        }
    }
    //  如果整个字符串的最后一个不是空字符，那么如果没有这个判断就会导致最后一个单词漏记
    if (isBegin) {
        String temp = s.substring(start, end);
        stack.push(temp);
    }

//  将栈中的单词组成一个翻转字符串
    while (stack.size() > 0) {
        sb.append(stack.pop());
        sb.append(" ");
    }
    //  将反转后的字符串返回（上面 sb 后面会多加一个空格，因此在返回字符串时需去掉 ）
    return sb.toString().substring(0, sb.length() - 1);
}
```

### 2.2 解法二：两次翻转

#### 2.2.1 问题分析

1. 该方法的基本思想是首先将字符串去除首尾的空格后进行翻转。
2. 然后遍历反转后的字符串，删除多余的空格，并将每个单词进行翻转。
3. 最后转换为字符串，直接返回即可。![](/media/202107/151-翻转字符串里的单词（解法二：两次翻转）_1625841097.gif)

#### 2.2.2 参考代码

```java
/**
 * 翻转一个单词
 * @param sb    字符串
 * @param start 单词起始位置
 * @param end   单词结束位置加 1
 * @return  翻转相应单词后的字符串
 */
public StringBuilder reverseWord(StringBuilder sb, int start, int end) {
    for (int i = start; i < (start + end) / 2; i++) {
        char temp = sb.charAt(i);
        int symmetricalPosition = start + end - i - 1;
        sb.setCharAt(i, sb.charAt(symmetricalPosition));
        sb.setCharAt(symmetricalPosition, temp);
    }
    return sb;
}

/**
 * 151. 翻转字符串里的单词（版本 2：两次翻转）
 *
 * @param s 字符串
 * @return 翻转后的字符串
 */
public String reverseWordsV2(String s) {
    if (s == null || s.trim() == "") {return "";}
    //  去除字符串两边的空格
    StringBuilder sb = new StringBuilder(s.trim());
    //  将字符串翻转
    sb = sb.reverse();
    int len = sb.length();

//  是否遇到空格
    boolean meetSpace = false;
    //  删除空格的数量
    int deleteSpaceCount = 0;
    //  要翻转的单词的起始位置
    int start = 0, end = 0;

//  遍历字符串，删除空格，并将所有的单词翻转
    for (int i = 0; i < len; i++) {
        if (sb.charAt(i - deleteSpaceCount) == ' ') {
            //  遇到了一个空格
            if (!meetSpace) {
                //  在这个单词前面没有遇到空格，说明这是但此后面的第一个空格，直接将 [start, end) 之间的单词进行翻转即可（注：start 和 end 为更正后的位置，即减去了删除空格的长度）
                end = i - deleteSpaceCount;
                start = start - deleteSpaceCount;
                sb = reverseWord(sb, start, end);
                meetSpace = true;
            } else {
                //  在这个单词前面已经遇到了空格，说明这个空格是空格后面的空格，直接删掉即可
                sb = sb.deleteCharAt(i - deleteSpaceCount);
                deleteSpaceCount++;
                meetSpace = true;
            }
        } else {
            //  不是空格
            if (meetSpace) {
                //  单词前面遇到了空格，说明这个是单词的第一个字符，直接重置 start 的位置，然后标记为未遇到空格
                start = i;
                meetSpace = false;
            }
        }
    }
    if (!meetSpace) {
        //  最后一个单词后面没有遇到空格，直接将最后一个单词进行翻转即可
        end = len - deleteSpaceCount;
        sb = reverseWord(sb, start - deleteSpaceCount, end);
    }
    //  返回结果
    return sb.toString();
}
```

## 3 参考文献

1. [151. 翻转字符串里的单词](https://leetcode-cn.com/problems/reverse-words-in-a-string)。
2. [原地翻转字符串里的单词(空间复杂度为 O(1))](https://leetcode-cn.com/problems/reverse-words-in-a-string/solution/yuan-di-fan-zhuan-zi-fu-chuan-li-de-dan-wbsaw)。