186.Reverse Words in a String II

Tags: Medium String

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

---

Given an input string , reverse the string word by word.

Example:

Input:  ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
Output: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]

Note:

• A word is defined as a sequence of non-space characters.
• The input string does not contain leading or trailing spaces.
• The words are always separated by a single space.

Follow up: Could you do it in-place without allocating extra space?

---

follow up部分要求只能使用常数空间，时间复杂度还要为$O(n)$，一种办法是先整体反转，然后反转单独的单词部分。

class Solution {
public:
    void reverseWords(vector<char>& s) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        reverse(s.begin(), s.end());
        int pre = 0;
        int n = s.size();

        for (int i = 0; i < n; ++i) {
            if (s[i] == ' ') {
                reverse(s.begin() + pre, s.begin() + i);
                pre = i + 1;
            }
        }
        reverse(s.begin() + pre, s.end());
    }
};