leecode第一百五十一题（ 翻转字符串里的单词）

class Solution {
public:
    string reverseWords(string s) {
        string res;
        stack<char> temp;//使用辅助栈做
        int len=s.size();
        if(len==0)
            return res;
        
        int index=len-1;
        while(index>=0&&s[index]==' ')
                index--;
        while(index>=0)
        {
            while(index>=0&&s[index]!=' ')
            {
                temp.push(s[index]);
                index--;
            }
                
            while(!temp.empty())
            {
                res.push_back(temp.top());
                temp.pop();
            }
            
            res.push_back(' ');
            
            while(index>=0&&s[index]==' ')
                index--;
        }
        res.pop_back();
        return res;
    }
};

class Solution {
public:
    string reverseWords(string s) {
        int len=s.size();
        if(len==0)
            return s;
        
        int index_sta=0;
        int index_end=len-1;
        while(index_sta!=index_end&&index_sta!=index_end+1)//全部反转
        {
            char temp;
            temp=s[index_sta];
            s[index_sta]=s[index_end];
            s[index_end]=temp;
            index_sta++;
            index_end--;
        }
        
        index_sta=0;
        index_end=index_sta;
        while(index_end<len)
        {
            while(index_end<len&&s[index_end]==' ')//检测下一个单词的初始位置
                index_end++;
            
            int index_temp_sta=index_end;//下个单词局部反转
            int index_temp_end=index_end;
            while(index_temp_end<len-1&&s[index_temp_end+1]!=' ')
                index_temp_end++;
            
            while(index_temp_sta!=index_temp_end&&index_temp_sta!=index_temp_end+1)
            {
                char temp;
                temp=s[index_temp_sta];
                s[index_temp_sta]=s[index_temp_end];
                s[index_temp_end]=temp;
                index_temp_sta++;
                index_temp_end--;
            }
            
            while(index_end<len&&s[index_end]!=' ')//单词往前挪
            {
                s[index_sta]=s[index_end];
                if(index_sta!=index_end)
                    s[index_end]=' ';
                index_sta++;
                index_end++;
            }
            
            s[index_sta]=' ';
            index_sta++;
        }
        
        index_sta--;
        while(index_sta>0&&s[index_sta-1]==' ')
            index_sta--;
        return s.substr(0,index_sta);
    }
};

分析：

第一个空间复杂度为线性阶，第二个则是常数阶，话说第二个还快点。。。所以第一个很尴尬。。。

第一个是栈实现，第二个是反转。