# 186. Reverse Words in a String II

## Description

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.

## Solutions

• class Solution {
public void reverseWords(char[] s) {
int n = s.length;
for (int i = 0, j = 0; j < n; ++j) {
if (s[j] == ' ') {
reverse(s, i, j - 1);
i = j + 1;
} else if (j == n - 1) {
reverse(s, i, j);
}
}
reverse(s, 0, n - 1);
}

private void reverse(char[] s, int i, int j) {
for (; i < j; ++i, --j) {
char t = s[i];
s[i] = s[j];
s[j] = t;
}
}
}

• class Solution {
public:
void reverseWords(vector<char>& s) {
int n = s.size();
for (int i = 0, j = 0; j < n; ++j) {
if (s[j] == ' ') {
reverse(s, i, j - 1);
i = j + 1;
} else if (j == n - 1) {
reverse(s, i, j);
}
}
reverse(s, 0, n - 1);
}

void reverse(vector<char>& s, int i, int j) {
for (; i < j; ++i, --j) {
swap(s[i], s[j]);
}
}
};

• class Solution:
def reverseWords(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""

def reverse(s, i, j):
while i < j:
s[i], s[j] = s[j], s[i]
i += 1
j -= 1

i, j, n = 0, 0, len(s)
while j < n:
if s[j] == ' ':
reverse(s, i, j - 1)
i = j + 1
elif j == n - 1:
reverse(s, i, j)
j += 1
reverse(s, 0, n - 1)


• func reverseWords(s []byte) {
n := len(s)
for i, j := 0, 0; j < n; j++ {
if s[j] == ' ' {
reverse(s, i, j-1)
i = j + 1
} else if j == n-1 {
reverse(s, i, j)
}
}
reverse(s, 0, n-1)
}

func reverse(s []byte, i, j int) {
for i < j {
s[i], s[j] = s[j], s[i]
i++
j--
}
}

• /**
Do not return anything, modify s in-place instead.
*/
function reverseWords(s: string[]): void {
const n = s.length;
const reverse = (i: number, j: number): void => {
for (; i < j; ++i, --j) {
[s[i], s[j]] = [s[j], s[i]];
}
};
for (let i = 0, j = 0; j <= n; ++j) {
if (s[j] === ' ') {
reverse(i, j - 1);
i = j + 1;
} else if (j === n - 1) {
reverse(i, j);
}
}
reverse(0, n - 1);
}