LC 151. Reverse Words in a String

https://leetcode.com/problems/reverse-words-in-a-string/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    string reverseWords(string s) {
        int n = s.size();
        for (int i = 0; i < n / 2; i++) {
            swap(s[i], s[n - 1 - i]);
        }
        int r = 0;
        while (r < n && s[r] == ' ') r += 1;
        while (r < n) {
            int l = r;
            while (r < n && s[r] != ' ') r += 1;
            for (int i = 0; i < (r - l) / 2; i++) {
                swap(s[i + l], s[r - i - 1]);
            }
            while (r < n && s[r] == ' ') r += 1;
        }
        int idx = 0;
        r = 0;
        while (r < n) {
            while (r < n && s[r] == ' ') r += 1;
            if (r < n && idx != 0) s[idx++] = ' ';
            while (r < n && s[r] != ' ') {
                s[idx++] = s[r++];
            }
        }
        s.resize(idx);
        return s;
    }
};

Time Complexity: O(n)
Space: O(1)

先將整個 string 翻轉，之後根據每個單字進行翻轉，最後把多餘的空白移除，這樣就可以做到 inplace 完成。