题目描述

给定一个字符串，请将它以word为单位逆序。

注意：

• 单词是指一段连续的非空格字符；
• 数据保证给定的字符串的开头和结尾不包含多余的空格；
• 数据保证所有单词之间仅有一个空格；

进一步： 能否使用原地算法，即只使用额外 $O(1)$ 的空间。

样例

输入：["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
输出：["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]

算法

(线性扫描，操作分解) $O(n)$

这道题目是leetcode 151. Reverse Words in a String的简化版本。

原问题直接操作比较困难，我们可以分成两步来做：

1. 先找出所有word，将word内部的字母逆序；
2. 然后再所有word逆序；

空间复杂度分析：所有逆序操作都基于两个字符的 swap() 函数，该函数只使用额外 $O(1)$ 的空间，所以我们整个程序也仅使用额外 $O(1)$ 的空间。
时间复杂度分析：整个数组仅被扫描3次，所以时间复杂度是 $O(n)$。

C++ 代码

class Solution {
public:
    void reverseWords(vector<char>& s) {
        for (int i = 0; i < s.size(); i ++ )
        {
            int j = i;
            while (j < s.size() && s[j] != ' ' ) j ++ ;
            for (int a = i, b = j - 1; a < b; a++, b--)
            {
                swap(s[a], s[b]);
            }
            i = j;
        }
        for (int i = 0, j = s.size() - 1; i < j; i++, j--)
        {
            swap(s[i], s[j]);
        }
    }
};