题解 | #翻转单词序列#

题解一：使用双指针。首先用左指针执行字符串的首元素，右指针执行字符串最后一个元素，然后将这两个元素调换位置，然后将两指针往里靠，继续替换，直到左指针大于等于右指针的位置。整体替换完后进行局部替换，先将两指针执行字符串首元素，然后遍历字符串，当遍历到空格或者\0字符串结束符，就进行局部替换，将右指针执行遍历到的元素的左边一个元素，然后开始循环替换。最后，更新左右指针，将左指针执行当前元素下一位，然后继续遍历。最后遍历完返回当前字符串。时间复杂度是O(n * n)。空间复杂度是O(1)。

class Solution {

  public:

    string ReverseSentence(string str) {

        if (str.empty())return string();

        int i = 0;

        int j = str.length() - 1;

        while (i < j) {

            char tmp = str[i];

            str[i] = str[j];

            str[j] = tmp;

            i += 1;

            j -= 1;

        }

        i = 0;

        j = 0;

        for ( j ; j <= str.length() ; j++) {

            int index = j;

            if (str[j] == ' ' || str[j] == '\0') {

                index -= 1;

                while (i < index) {

                    char tmp = str[i];

                    str[i] = str[index];

                    str[index] = tmp;

                    i ++;

                    index --;

                }

                i = j + 1;

            }

        }

        return str;

    }

};

题解二：使用辅助栈，栈中存的元素是字符串。首先，遍历字符串，将每个单词压入栈中，最后再将栈中的元素一一弹出，然后拼接，最后返回拼接后的字符串即使结果。如何识别每个单词并分割压入栈呢？首先用快慢指针，慢指针一开始执行字符串首元素，然后快指针负责遍历字符串，找到空格或者是字符串结束符，找到后使用substr进行分割，压入栈，最后更新慢指针位置，将慢指针指向快指针的下一位，当遇到的是空格，将空格也压入栈。最后遍历栈，将栈中元素一一弹出并拼接。时间复杂度是O(n)，空间复杂度是O(n)。

lass Solution {

  public:

    string ReverseSentence(string str) {

        if(str.empty())return string();

        //借助辅助栈

        stack<string> stack1;

        int index = 0;

        int i = 0;

        for(i;i <= str.size();i++){

            if(str[i] == ' ' || str[i] == '\0'){

                stack1.push(str.substr(index,i - index));

                index = i + 1;

                if(str[i] == ' ')stack1.push(str.substr(i,1));

            }

        }

        str.clear();

        while(!stack1.empty()){

            str += stack1.top();stack1.pop();

        }

        return str;

    }

};