力扣151题（字符串，双指针）

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/reverse-words-in-a-string

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

151.给你一个字符串 s ，逐个翻转字符串中的所有单词 。单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。

说明：

输入字符串 s 可以在前面、后面或者单词间包含多余的空格。

翻转后单词间应当仅用一个空格分隔。

翻转后的字符串中不应包含额外的空格。

1. 在第一步删除多余空格时就犯了难，题解用的是快慢指针，快慢指针同时指向字符串头，然后快指针往前走到第一个不是空格的字符就将快指针指向的字符赋值给慢指针指向的字符，然后慢指针往前走一步，这就完成了删除字符串前面多余的字符；然后快指针接着往前走，如果遇到连续的空格就只赋值一次给慢指针指向的字符；这样走下来，慢指针最终指向的字符可能是一个空格，如果是空格的话在返回新字符串的时候就不要留下这个空格，这里返回新字符串题解用的C++使用了字符串的string的resize方法，而我用的C，就直接创建一个新字符串来进行赋值操作了。
2. 删除了多余空格后，只需要将整个字符串反转一遍，然后再对字符串中的每个单词进行反转一遍，这里比较难的地方在于如何界定每个单词的区间。这里使用了一个布尔变量来标记是否进入了单词的区间，还未进入时循环变量所在的位置就是单词的开头位置，进入后当循环变量到达空格符的位置时，循环变量前一个位置就是单词的结束位置。此外还需要额外写一段代码处理最后一个单词后面没有空格符的情况。

char* removeExtraSpaces(char * s) {
    int slowIndex = 0, fastIndex = 0;
    //去除字符串前面的空格
    while (strlen(s) > 0 && fastIndex < strlen(s) && s[fastIndex] == ' ') {
        fastIndex++;
    }
    //去除掉字符串间多余的空格
    while (fastIndex < strlen(s)) {
        if (fastIndex - 1 > 0 && s[fastIndex] == ' ' && s[fastIndex] == s[fastIndex - 1]) {
            fastIndex++;
            continue;
        } else {
            s[slowIndex++] = s[fastIndex++];
        }
    }
    //去除字符串末尾的空格,经过上面那步末尾可能有一个空格或没有空格
    if (slowIndex - 1 > 0 && s[slowIndex - 1] == ' ') {
        char* newString = (char*)malloc(sizeof(char) * slowIndex);
        int i = 0;
        for (; i < slowIndex - 1; i++) {
            newString[i] = s[i];
        }
        newString[i] = '\0';
        return newString;
    } else {
        char* newString = (char*)malloc(sizeof(char) * (slowIndex + 1));
        int i = 0;
        for (; i < slowIndex; i++) {
            newString[i] = s[i];
        }
        newString[i] = '\0';
        return newString;
    } 
}

//反转字符串指定区间
void reverse(char *s, int start, int end) {
    int i = start, j = end;
    char temp;
    while (i < j) {
        temp = s[i];
        s[i] = s[j];
        s[j] = temp;
        i++, j--;
    }
}

char * reverseWords(char * s){
    //移除多余空格
    s = removeExtraSpaces(s);
    //反转整个句子
    reverse(s, 0 , strlen(s) - 1);
    //反转句子中的单词
    bool entry = false;//标记枚举字符串时是否进入了单词区间
    int start = 0, end = 0;//用于标记每个需要反转的区间
    for (int i = 0; i < strlen(s); i++) {
        if ((!entry)) {
            start = i;
            entry = true;
        }
        //遇到空格就是单词分隔符
        if (entry && s[i] == ' ') {
            end = i - 1;
            entry = false;
            reverse(s, start, end);
        }
        //最后一个空格后面没有分隔符
        if (entry && (i == strlen(s) - 1)) {
            end = i;
            entry = false;
            reverse(s, start, end);
        }
    }
    return s;
}