Reverse Words in a String

151. 反转字符串中的单词

分析

去除多余空格：
- 遍历字符串，将所有单词移动到前面，同时移除多余的空格
- 用一个变量 k 表示当前写入位置
逐个反转单词：
- 每次遇到非空格字符时，确定单词的起始位置 i
- 继续遍历直到单词结束，将单词拷贝到字符串前面
- 对该单词的字符进行局部反转
- 在单词末尾添加空格，准备下一个单词的处理
清理末尾多余空格：
- 如果最后多余了一个空格，则将其删除
整体反转字符串：
- 将整个字符串反转，得到单词顺序颠倒的最终结果

时间复杂度

遍历字符串三次：去除多余空格 O(n)、单词局部反转 O(n)、整体反转 O(n)

总时间复杂度为 O(n)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


class Solution
{
public:
    string reverseWords(string s)
    {
        int k = 0; // 表示当前写入位置
        for (int i = 0; i < s.size(); ++i)
        {
            // 跳过空格
            if (s[i] == ' ')
                continue;

            // 找到单词的起始位置
            int j = i, t = k;
            while (j < s.size() && s[j] != ' ')
                s[t++] = s[j++];

            // 反转单词
            std::reverse(s.begin() + k, s.begin() + t);

            // 在末尾添加一个空格
            s[t++] = ' ';
            k = t; // 更新写入位置
            i = j; // 跳过当前单词
        }

        // 删除末尾多余的空格
        if (k > 0)
            --k;
        s.erase(s.begin() + k, s.end());

        // 整体反转字符串
        std::reverse(s.begin(), s.end());

        return s;
    }
};