题解 | #翻转单词序列#

题解一： 原地操作法
解题思路：将后面的字符插入到前面。
主要思路：
1.使用两个指针:cur_end与 cur_insert , cur_end表示当前字符串末尾位置，cur_insert表示当前插入位置。
2. 从尾至头处理str,cur_end分为三种情况
a.如果cur_end指向的是空字符且上次处理的字符非空，那么将cur_end指向的字符插入到cur_insert同时删除cur_end所指字符。
b. 如果cur_end指向非空字符，那么cur_end指向的字符插入到cur_insert同时删除cur_end所指字符。
c.如果cur_end指向空字符且上一次处理的字符也为空字符，那么直接删除cur_end所指字符。

复杂度分析：
时间复杂度：O(N)
空间复杂度：O(1)

实现如下：

class Solution {
public:
   string ReverseSentence(string str) {
        if(str=="") return str;
        int cur_insert = 0; //插入位置
        int cur_end = str.size()-1;
        int former_pro = 1;  //上次处理的字符是否为空格
        int num = 0; //处理个数；
        for(int i = str.size();i>0;i--)
        {
            if(former_pro && str[cur_end] ==' ')
            {
                str.erase(cur_end--,1);
                former_pro = 1;
            }
            else if(!former_pro && str[cur_end]==' ')
            {
                cur_insert = num++;
                str.insert(cur_insert++,1,str[cur_end++]);
                str.erase(cur_end--,1);
                former_pro = 1;
            }
            else
            {
                num++;
                //连续的单词插入位置不能变，不然单词就会是反的
                str.insert(cur_insert,1,str[cur_end++]);
                str.erase(cur_end--,1);
                former_pro = 0;
            }
        }
        return str;
    }
};

题解二：双指针
解题思路： 利用两个指针标识一个单词。
主要思路：

1. 从尾往头遍历 使用left表示一个单词的起始位置，right表示一个单词的终止位置。
2. 当遇到空格left与right同时向前移动，当遇到字符只有left向前移动，截取[left+1,right] 子串。
3. 拼接截取下的字符串。

复杂度分析：
时间复杂度： O(N)
空间复杂度： O(N)

实现如下：

class Solution {
public:
    string ReverseSentence(string str) {
       int left = str.size() - 1;
        int right = str.size() - 1;
        string result = "";
        while (left >= 0)
        {
            while (str[left] == ' ')
            {
                --left;
                --right;
                if (left < 0) //越界
                {
                    break;
                }
            }
            if (left < 0) //越界
            {
                break;
            }
            while (str[left] != ' ')
            {
                --left;
                if (left < 0) //越界
                {
                    break;
                }
            }
            result = result + str.substr(left + 1, right - left) + " ";
            right = left;
        }
        return result.substr(0, result.size() - 1); // 结果后面会多一个空格
}
};

题解三： 使用栈
解题思路： 使用栈保存单词，当遇到空格将栈中的字符全部弹出。每弹出一个完成单词添加一个空格。

复杂度分析：
时间复杂度：O(N)
空间复杂度：O(N)，使用stack存储每一个单词，需要O(n)空间

class Solution {
public:
    string ReverseSentence(string str) {
        stack<char> st;//临时存储每个字符
        string result ="";//结果
        for(int i = str.size()-1;i>=0;i--)
        {
            if(str[i] != ' ')
            {
                st.push(str[i]);
            }
            if(str[i] == ' ' || i==0)
            {    
                //出栈
                int ok = 0;//标记是否出栈
                while(!st.empty())
                {
                    result.push_back(st.top());
                    st.pop();
                    ok = 1;//出栈
                }
                if(ok) result += " ";//有出栈，添加空格；
            }
        }
                return result.substr(0,result.size()-1);
    }
};