题目

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

代码 （包含官解+自解+ python api trick）

//官方的正解类似于一种双指针的模拟
//idx 每一次都跑到最后一个单词的末尾 start则继续去寻找下一个单词 
//找到了下一个单词 用idx填充一个空格并移动到下一个单词的头部 
//end与start交换用于单词的原地读入与反转
//最后erase用于清除string s 后面可能存在的空格
class Solution {
public:
    string reverseWords(string s) {
        // 反转整个字符串
        reverse(s.begin(), s.end());

        int n = s.size();
        int idx = 0;
        for (int start = 0; start < n; ++start) {
            if (s[start] != ' ') {
                // 填一个空白字符然后将idx移动到下一个单词的开头位置
                if (idx != 0) s[idx++] = ' ';

                // 循环遍历至单词的末尾
                int end = start;
                while (end < n && s[end] != ' ') s[idx++] = s[end++];

                // 反转整个单词
                reverse(s.begin() + idx - (end - start), s.begin() + idx);

                // 更新start，去找下一个单词
                start = end;
            }
        }
        s.erase(s.begin() + idx, s.end());
        return s;
    }
};

// 自拟答案——TLE 
// class Solution {
// public:
//     vector<string> vec;
//     string reverseWords(string s) {
//         int n = s.length();
//         string res = "";
//         for(int i = 0;i < n;i++)
//         {
//             string son = "";
//             if(s[i] == ' ') break;
//             while(s[i] != ' ')
//             {
//                 son += s[i];
//             }
//             vec.push_back(son);
//         }
//         int n2 = vec.size();
//         for(int i = n2 - 1;i >= 0;i--)
//         {
//             res = vec[i] + ' ';
//             if(i == 0) res += vec[0];
//         }
//         return res;
//     }
// };

// python 使用库函数可以直接秒
// class Solution  
//     def reverseWords(self,s : str)-> str:
//         return " ".join(reversed(s.split()))