186

186. Reverse Words in a String II (Medium)

Given a character array s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by a single space.

Your code must solve the problem in-place, i.e. without allocating extra space.

 

Example 1:

Input: s = ["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"]

Example 2:

Input: s = ["a"]
Output: ["a"]

 

Constraints:

• 1 <= s.length <= 105
• s[i] is an English letter (uppercase or lowercase), digit, or space ' '.
• There is at least one word in s.
• s does not contain leading or trailing spaces.
• All the words in s are guaranteed to be separated by a single space.

Companies:
Microsoft

Related Topics:
Two Pointers, String

Similar Questions:

• Reverse Words in a String (Medium)
• Rotate Array (Medium)

Solution 1. Two Pointers

// OJ: https://leetcode.com/problems/reverse-words-in-a-string-ii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    void reverseWords(vector<char>& s) {
        int i = 0, N = s.size();
        while (i < N) {
            int start = i;
            while (i < N && s[i] != ' ') ++i;
            reverse(begin(s) + start, begin(s) + i);
            ++i;
        }
        reverse(begin(s), end(s));
    }
};