进出栈法：栈完成倒序

• 利用栈来完成字符串的倒序
• 字符串的切片用substr（pos,len)，切片出从pos开始的长度为len出的新字符串
• 原字符串加" "使得最后字符串片段不用特殊处理
• 别忘加空格，最后一个切片不用加

class Solution {
public:
    string ReverseSentence(string str) {
        if(str.empty())
        {
            return str;
        }
        stack<string> st;
        int start=0;
        str+=" ";
        for(int i=0;i<str.size();i++)
        {
            if(str[i]==' ')
            {
                st.push(str.substr(start,i-start));
                start=i+1;
            }
        }

        str="";
        while(st.size())
        {
            str+=st.top();
            st.pop();
            if(st.size())
            {
                str+=" ";
            }
        }
        return str;
    }
};

字符二次翻转法

• 空间想像力和经验
• 翻转整体字符串，再翻转部分字符串片段
• reverse(start,end) 翻转不包括end，在原字符串翻转

class Solution {
public:
    string ReverseSentence(string str) {
       //reverse
       if(str.empty())
       {
        return str;
       } 
       reverse(str.begin(),str.end());
       int start=0;
       for(int i=0;i<str.size();i++)
       {
            if(str[i]==' ')
            {
                reverse(str.begin()+start,str.begin()+i);
                start=i+1;
            }
       }
       reverse(str.begin()+start,str.end());
       return str;
    }
};