/*
 * 151. Reverse Words in a String
 *  Given an input string, reverse the string word by word.
For example,
Given s = "the sky is blue",
return "blue is sky the".

Update (2015-02-12):
For C programmers: Try to solve it in-place in O(1) space.
 Clarification:
What constitutes a word?
A sequence of non-space characters constitutes a word.
Could the input string contain leading or trailing spaces?
Yes. However, your reversed string should not contain leading or trailing spaces.
How about multiple spaces between two words?
Reduce them to a single space in the reversed string.

 Thinking:
  1. 先翻轉(zhuǎn)整個(gè)字符，然后按單個(gè)字符翻轉(zhuǎn)回來(lái)。
  2. 接下來(lái)主要考慮去掉頭尾空格和把中間多個(gè)空格變成一個(gè)的問(wèn)題。
  由于有空格的長(zhǎng)度始終比沒(méi)有空格的長(zhǎng)度長(zhǎng)，只需要記住每次應(yīng)該放置的位置
  和找到應(yīng)該放置的單詞區(qū)間，逐一放置到對(duì)應(yīng)的位置。
  例如：
  ————————————————————————————————————————————————
     _____     ____    非空格
  __|    |____|        空格
——————————————————————————————————————————————————
  _ab__c_
  找到第一個(gè)單詞后面的位置，記錄下來(lái)，然后把單詞前移，保證是單詞+1個(gè)空格的格式
  例如首先應(yīng)該開(kāi)始防止單詞的位置為start = 0， 然后往后找，找到出現(xiàn)單詞和再出現(xiàn)空格的位置，
  這里是begin = 1 和end = 3，然后把s[1],s[2] 和 空格 放到開(kāi)始位置，于是開(kāi)始
  位置變成了start = 3,繼續(xù)重復(fù)
 * */

void reverseWordsWithRange(char *s, int startPos, int length) {
    if (length > 1) {
        for (int i = 0; i < length / 2; i++) {
            char tmp = *(s + startPos + i);
            *(s + startPos + i) = *(s + startPos + length - 1 - i);
            *(s + startPos + length - 1 - i) = tmp;
        }
    }
}

//減少頭尾空格，縮減中間空格到1個(gè)
void reduceSpace(char *s) {
    int startPos = 0; //每次添加應(yīng)該添加到的位置

    int wordbegin = 0; //單詞的開(kāi)始位置，從空格到非空格開(kāi)始設(shè)置，從非空格到空格或者到達(dá)末尾重置
    int wordLength = 0; //每個(gè)單詞的長(zhǎng)度，非空格的遍歷過(guò)程中+1，從非空格到空格或者到達(dá)末尾重置

    int length = strlen(s);
    //從左到右順序遍歷，一旦出現(xiàn)波峰或者波谷則處理，最后在根據(jù)長(zhǎng)度設(shè)置結(jié)束標(biāo)志
    //波谷->波峰
//    {
//        wordbegin = i;
//        wordLength++;
//    }
    //波峰->波谷
//    {
//        wordLength = 0;
//        wordbegin = 0;
//    }

    char switchChar = ' ';
    char beforeChar = ' ';
    for (int i = 0; i < length; i++) {
        //找到下一個(gè)波谷
        char currentChar = s[i];
        //之前是空格，并且當(dāng)前不等于空格，則到達(dá)波峰
        if (beforeChar == switchChar && beforeChar != currentChar) {
            wordbegin = i;
        }

        if (currentChar != switchChar) {
            wordLength++;
        }
        //之前不是空格，當(dāng)前是空格，或者到達(dá)結(jié)尾, 此處要開(kāi)始執(zhí)行拷貝賦值流程
        if ((beforeChar != switchChar && currentChar == switchChar) ||
                (i == length -1 && currentChar != switchChar) ) {
            for (int i = 0; i < wordLength; i++) {
                s[startPos++] = s[wordbegin + i];
            }
            if (startPos < length) {
                s[startPos++] = switchChar;
            }
            wordLength = 0;
        }


        beforeChar = currentChar;
    }

    if (startPos > 1 && s[startPos - 1] == switchChar) {
        s[startPos - 1] = '\0';
    }
    if (startPos == 0 && startPos < length) {
        s[startPos] = '\0';
    }
}

void reverseWords(char *s) {
    int length = strlen(s);
    reverseWordsWithRange(s, 0, length);

    int startPos = 0;
    int endPos = 0;
    for (int i = 0; i < length; i++) {
        //找到空格或者到達(dá)末尾
        if (s[i] == ' ' || i == length - 1) {
            endPos = i;
            if (i == length - 1) {
                endPos = length;
            }
            reverseWordsWithRange(s, startPos, (endPos - startPos));
            startPos = endPos + 1;
        }
    }
    printf("%s\n", s);
    reduceSpace(s);
    printf("%s\n", s);
}