题目

题解

1. 双旋转单擦除法

题目要求空间复杂度$O(1)$，该方法符合，即先整体翻转全部字符串，再逐个单词串翻转，空格跳过，不同单词之间的空格自己添加

  • 时间复杂度$O(n)$
  • 空间复杂度$O(1)$
class Solution {
public:
    string reverseWords(string s) {
        if(s.empty()) return s;
        reverse(s.begin(),s.end());
        //由于需要跳过空格，需要将非空格的字符复制到前面，所以这里设置个index，表示已经复制的位数
        // index后的直接删除
        int index=0;
        for(int start=0; start<s.size(); start++){
            if(s[start] != ' '){//空字符跳过
                if(index != 0 ) s[index++] = ' ';//若遇到第二个字符串，则需要在原来的字符串上加一个空格，再加后面的
                int end = start;//end和start是当前字符串的首尾
                while(end < s.size() && s[end] != ' ') s[index++] = s[end++];//找到该字符串的末尾，并存到index之前
                //再把这个字符串翻转回来
                //注意翻转的区间，前者end-start是该子字符串的长度，index指向子字符串的末尾
                reverse(s.begin()+index-(end-start), s.begin()+index);
                start = end;//start从end处开始
            }
        }
        s.erase(s.begin()+index, s.end());//index后面的字符全部清除
        return s;
    }
};

2. stringstream法1

用stringstream处理字符串，getline分分隔字符串，重新排列

  • 时间复杂度$O(n)$
  • 空间复杂度$O(n)$
class Solution {
public:
    string reverseWords(string s) {
        stringstream ss(s);
        s = "";
        string tmp;
        while(getline(ss,tmp,' ')){//用空格分隔
            if(tmp.empty()) continue;//为空跳过
            s = (s.empty()? tmp : (tmp+" "+s));//非空格判断，第一个直接加上tmp，后面的在前面加上tmp并加上空格
        }
        return s;
    }
};

3. stringstream法2

用stringstream处理字符串，»输出字符，，重新排列

  • 时间复杂度$O(n)$
  • 空间复杂度$O(n)$
class Solution {
public:
    string reverseWords(string s) {
        stringstream ss(s);
        //输出流应该是会覆盖原有变量（存疑）
        ss>>s;//先存第一个单词
        string tmp;//暂存每个子字符串
        while(ss>>tmp) s = tmp+" "+s;//存接下来的单词，ss没输出完就一直遍历
        if(s[0]==' ') s="";//若初始s只有空格，直接清空
        return s;
    }
};