剑指Offer 58-I. 翻转单词顺序

剑指Offer 58

string reverseWords(string s) {
    string w, tmp;                           // w 表示翻转后的字符串，tmp 表示当前的单词
    int i = 0, j = s.size() - 1;             // 从后往前找单词，i是单词开头的前一个位置，j是单词最后一个位置

    while(i <= j && i >= 0) { 
        while(j > 0 && s[j] == ' ')  { j--; }   //遍历，如果当前是空格则继续找
        i = j-1;                                // i从j的前一个位置开始找
        while(i >= 0 && s[i] != ' ') { i--; }   //遍历，直到遇到第一个空格，说明分出了一个单词

        for(int q = i+1; q <= j; q++) {
            if(s[q] == ' ') continue;        // 防止空格混入其中， 比如有多个空格之前的判断就会传入单个空格
            tmp.append(1, s[q]);
        }

        if(w.size() > 0 && tmp.size() > 0) { // 如果是一串空格，那么 tmp.size() == 0
            tmp = " " + tmp;                 //在新单词前加空格，避免在句末添加无用的空格
        }

        w.append(tmp);                       // 加入翻转后的字符串中
        tmp = "";                            // 清空
        j = i-1;                             //更新 j 的位置，从上一个单词前面的空格的前一个位置开始，比如"hello world",添加完 world，j 的位置就是 o
        i--;
    }

    return w;
}