题目的主要信息：

对字符串中的所有单词进行倒排。

非构成单词的字符均视为单词间隔符；
倒排后的单词间隔符以一个空格表示；如果原字符串中相邻单词间有多个间隔符时，倒排转换后也只允许出现一个空格间隔符；

方法一：

逐个字符输入，用string变量word记录每一个单词，ans保存输出的结果。首先判断当前字符是否为字母，若为字母，则加到word中；若不为字母，说明到了单词的结尾，需要把当前的单词word加到ans中。若ans为空，说明之前还没有单词加入，那么直接把word放到ans里就好了；若ans不为空，说明之前已经有单词加入了，当前的单词要放在ans的前面，并且以空格隔开。word加到ans以后清空word的值，便于记录下一个单词。 alt

具体做法：

#include <iostream>
#include <string>

using namespace std;

int main()
{
    char c;
    string ans;
    string word;
    while(cin.get(c))//逐个字符输入
    {
        if(isalpha(c)) word+=c;//判断是否是英文字母，如果是的话加到单词里
        else{
            if(!word.empty()){//若有单词还没加入
                if(!ans.empty()){//ans不为空，word加入的时候需要添加空格
                    ans=word+' '+ans;
                }else{//若ans为空，直接加入word
                    ans=word;
                }
            }
            word.clear();//word已经加入了结果中，清空
        }
    }
    cout<<ans<<endl;
    return 0;
}

复杂度分析：

时间复杂度： $O (n)$ ，需要遍历一遍输入的字符串。
空间复杂度： $O (1)$ ，只用了常数空间。

方法二：

输入的字符串中除了空格还有其他字符，首先我们将其他字符转换为空格，然后按照空格分割整个字符串，得到储存每一个单词的vector，倒序输出这个vector。特别注意的地方是最后一个单词输出后不需要再输出空格了，因此单独考虑最后一个单词的输出。

具体做法：

#include<iostream>
#include<string>
#include<sstream>
#include<vector>

using namespace std;

int main()
{
    string str;
    vector<string> word;//保存所有单词
    getline(cin,str);
    for(int i=0;i<str.size();i++){//将其他字符转为空格
        if(!isalpha(str[i])){
            str[i]=' ';
        }
    }
    stringstream input(str);
    while(input>>str){//按照空格分割字符串
        word.push_back(str);
    }
    for(int i=word.size()-1;i>0;i--){//倒序输出
        cout<<word[i]<<" ";
    }
    cout<<word[0];//最后一个单词不需要输出空格，因此单独输出
    return 0;
}

复杂度分析：

时间复杂度： $O (n)$ ，需要遍历一遍输入的字符串。
空间复杂度： $O (n)$ ，最坏情况下为‘英文字符英文字符英文字符’，word的大小为 $O (n)$ 。

题解 | #单词倒排#

题目的主要信息：

方法一：

方法二：