描述

题目描述

给定一个字符串以空格分隔，以每一个单词为一个单位，反转整个字符串

样例解释

样例输入：

"nowcoder. a am I"

然后我们很容易得到，我们是这么四个单词

nowcoder. 
a 
am 
I

然后我们反转得到我们的样例输出

"I am a nowcoder."

解法

解法一：C++的字符流

解题思路：

我们可以直接使用C++的库函数，将字符以空格分隔，然后颠倒输出

然后我们这里使用了stringstream

由于stringstream构造函数会特别消耗内存，似乎不打算主动释放内存(或许是为了提高效率)，但如果你要在程序中用同一个流，反复读写大量的数据，将会造成大量的内存消耗，因些这时候，需要适时地清除一下缓冲 (用 stream.str("") )。

代码实现：

class Solution {
public:
    string ReverseSentence(string str) {
        if (str.size() == 0) return "";
//         如果字符串为空，直接返回空
        vector<string> res;
//         这个是我们存储最后的答案的
        string tmp;
//         临时字符串
        stringstream sc(str);
//         字符流
        while (sc >> tmp) res.push_back(tmp);
//         分割之后放到数组
        reverse(res.begin(), res.end());
//         反转
        tmp = "";
        for (int i = 0; i < res.size(); i++) {
            tmp += res[i];
            if (i != res.size() - 1) tmp += " ";
//             不是最后一个的话，加一个空格最后一个不加
        }
        return tmp;
    }
};

时空复杂度分析

时间复杂度： $O(n)O(n)$

理由如下：因为我们实际上最多就是遍历字符串，无额外时间

空间复杂度： $O(n)O(n)$

理由如下：这里我们只是简单的考虑了我们的构造的这个答案数组的大小，然后不考虑我们的字符流的内存消耗

解法二：手动去除空格

解题思路：

我们可以直接进行判断，每次遇到空格的时候，我们就可以是把临时字符串存起来，然后最后颠倒，输出

图解代码

代码实现：

class Solution {
public:
    string ReverseSentence(string str) {
        if (str.size() == 0) return "";
//         如果为空直接返回空
        vector<string> res;
//         答案
        string tmp = "";
//         临时字符串
        for (auto &it : str) {
            if (it == ' ') {
                if (tmp != " ") res.push_back(tmp), tmp = "";
//                 如果我们这次遇到了空格，并且我们的字符串不是空格，存入答案，清空临时字符串
            } else {
                tmp += it;
//                 增加字符串
            }
        }
        if (tmp != " ") res.push_back(tmp);
//         如果最后一位有值，记得存入
        string ans = "";
        reverse(res.begin(), res.end());
        for (int i = 0; i < res.size(); i++) {
            ans += res[i];
            if (i != res.size() - 1) ans += " ";
        }
//         构造我们最后的答案字符串
        return ans;
    }
};

时间复杂度： $O(n)O(n)$

理由如下：因为我们实际上最多就是遍历字符串，无额外时间

空间复杂度： $O(n)O(n)$

理由如下：这里我们只是关于构造的这个答案数组的大小