题目链接：AcWing 77. 翻转单词顺序

一、题解

思路一：

  1. 开一个额外的字符串来存储每个单词
  2. 倒序进行扫描一遍，然后进行拼接res += tmp + " "即可
  3. 最后记得还要进行一次res += tmp

时间复杂度：O(n)

空间复杂度：O(n)

可以参考代码一！

思路二：

思路一很明显使用了额外的空间，更优的做法是不使用额外的空间进行原地处理！

  1. 可以先将整个字符串进行反转
  2. 然后对每一个单词进行反转即可

时间复杂度：O(n)

空间复杂度：O(1)

参考代码二！

二、AC代码

参考代码一：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    string reverseWords(string s) {
        string res, tmp;
        for(int i = s.size() - 1; i >= 0; i --){
            if(s[i] == ' ') res += tmp + " ", tmp = "";
            else tmp = s[i] + tmp;
        }
        res += tmp;
        return res;
    }
};

参考代码二：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    string reverseWords(string s) {
        reverse(s.begin(), s.end());
        for(int i = 0; i < s.size(); i ++){
            int j = i;
            while(j < s.size() && s[j] != ' ') j ++;
            reverse(s.begin() + i, s.begin() + j);
            i = j;
        }
        return s;
    }
};