题目：151.翻转字符串里的单词

给定一个字符串，逐个翻转字符串中的每个单词。不能存在任何"多余的"空格

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

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

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

整体思路

如果使用额外空间本题难度就很低了，下面讨论如何不使用额外空间解决

这里和上一题一样，实际上是考察对字符串(或者说数组)本身进行变换的能力。首先对这类不熟悉的题目心中要有信念：我们第一优先级的思路一定是往我们熟知的手法靠拢，是由新题目找老手法，而不是临场创造手法。

这样就能想到这个思路：将字符串整体反转，再将每个单词逐个反转即可。如果没有多余空格，上述操作会非常简单。但这题另一个难点就是处理多余空格。

如何去掉多余空格

既然是"去掉"空格，首先想到的就是先判断空格是否多余，然后直接删除多余空格。这个操作会用到erase()。但仔细想想就能发现，erase()的时间复杂度是O(n)，因为它需要重新移动一部分元素来保证元素连续。这样的话整体复杂度又被拉到O(n²)了

我们发现删除所有多余空格时，需要移动的元素方向是相同的，都是向前移动。以最后一个元素为例，如果它的终点是下标为0的位置，那么使用erase()它最终需要移动n次。但实际上我们只需要进行一次移动就可以把它放在正确的位置。

因此，我们的思路可以转变一下：我们以单词为单位将它们前移，并在移动过程中跳过多余的空格即可。具体来说：

• 设置两个指针start和end，用于标识当前处理的单词的开头和结尾。

• 设置一个指针idx，从头到尾遍历一遍字符串，标识当前正确的空位

• idx置0，start和end去遍历寻找下一个单词的开头结尾

  • idx为0时，正在处理第一个单词。此时直接把start和end之间的字符赋值到idx开始的等长部分

  • idx不为0时候，先为idx赋值空格，表示单词之间的空格。再把start和end之间的字符赋值到idx+1开始的等长部分

• 令end++，再令start = end，然后去寻找下一个单词

• 最后多余的空格都会出现在字符串的末尾，通过resize()或erase()处理。

void removeSpace(string& s) {
    int start = 0; int end = 0; int n = s.size();
    int idx = 0;
    while (end < n) {
        //while每次循环都是处理一个新的单词，所以除了第一个单词之外都需要在开头加上空格
        if (idx != 0) {
            s[idx++] = ' ';
        }
        //找到下一个单词的起点
        while (start < n && s[start] == ' ') {
            start++;
        }
        end = start;
        //从start开始遍历这个单词，将每个字符依次赋值给idx之后的部分
        while (end < n && s[end] != ' ') {
            s[idx++] = s[end++];
        }
        //更新start，准备下一轮处理
        start = end;
    }
    //删除集中在尾部的多余空格
    s.erase(s.begin() + idx, s.end());
}

反转

接下来的操作就很简单了，把去掉空格之后的字符串整体反转再按单词反转即可：

void removeSpace(string& s) {
    int start = 0; int end = 0; int n = s.size();
    int idx = 0;
    while (end < n) {
        //while每次循环都是处理一个新的单词，所以除了第一个单词之外都需要在开头加上空格
        if (idx != 0) {
            s[idx++] = ' ';
        }
        //找到下一个单词的起点
        while (start < n && s[start] == ' ') {
            start++;
        }
        end = start;
        //从start开始遍历这个单词，将每个字符依次赋值给idx之后的部分
        while (end < n && s[end] != ' ') {
            s[idx++] = s[end++];
        }
        //更新start，准备下一轮处理
        start = end;
    }
    //删除集中在尾部的多余空格
    s.erase(s.begin() + idx, s.end());
}

string reverseWords(string s) {
    removeSpace(s); //去除多余空格，保证单词之间之只有一个空格，且字符串首尾没空格。
    reverse(s.begin(),s.end());
    int start = 0; //removeSpace后保证第一个单词的开始下标一定是0。
    for (int i = 0; i <= s.size(); ++i) {
        if (i == s.size() || s[i] == ' ') { //到达空格或者串尾，说明一个单词结束。进行翻转。
            reverse(s.begin()+start,s.begin()+i); //翻转，注意是左闭右闭 []的翻转。
            start = i + 1; //更新下一个单词的开始下标start
        }
    }
    return s;
}