原题连接

https://leetcode.cn/problems/reverse-words-in-a-string-ii/description/

基本思路

先反转整个字符串，再依次反转每一个单词。

反转字符串时间复杂度O(n)，遍历字符串找单词、反转每个单词时间复杂度O(n)，总时间复杂度O(n)，总空间复杂度O(1)

代码

class Solution {
public:
    void reverseWords(vector<char>& s) {
        // 单空格为单词分界
        // 只反转单词顺序，不反转单词
        // Solution: 先反转字符串，再反转每个单词
        if (s.empty() || s.size() == 1) return;
        reverse(s.begin(), s.end());
        int i = 0, j = 0;  // i为单词左节点，j为单词右节点
        while (i < s.size()) {  // 用j遍历数组，j值一定要变
            if (j != s.size()) if (s[j] != ' ') {  // 当j没越界且j不为空格的时候，说明j在单词内部，继续移动j
                j++; continue;
            }
            // j越界或j为空格，反转单词
            for (int l = i, r = j - 1; l < r; ++l, --r) swap(s[l], s[r]);
            i = ++j;  // 此时j在空格处，j右移到下一个单词首字母，再将i移动到同样的位置
        }
    }
};