题解 | #翻转单词序列#

思路：

利用栈的先入后出的特性，用一个元素为字符串的栈将字符串依据空格拆分出的单词先入栈再出栈即可； 代码如下：

class Solution {
public:
    string ReverseSentence(string str) {
        stack<string> stk;
        int sz=str.size();
        string ret="";
        for(int i=0;i<sz;++i){
            string stmp="";
            while(i<sz && str[i]!=' '){
                stmp+=str[i];
                ++i;
            }
            if(stmp!=""){
                stk.push(stmp);
            }
        }
        while(!stk.empty()){
            ret+=stk.top();
            stk.pop();
            if(!stk.empty()) ret+=' ';//注意省去末尾空格
        }
        return ret;
    }
};

• 时间复杂度： 遍历完所有字母因此为O(N)；
• 空间复杂度： 申请了一个额外的栈空间，最坏情况下也为O(N)