力扣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;
}