LeetCode 0186. Reverse Words in a String II Solution in Java, C++, Python & More | Explanation + Code

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

Solution 1: Two Pointers

We can iterate through the character array s, using two pointers i and j to find the start and end positions of each word, then reverse each word, and finally reverse the entire character array.

The time complexity is O(n), where n is the length of the character array s. The space complexity is O(1).

PythonJavaC++GoTypeScript

class Solution: def reverseWords(self, s: List[str]) -> None: def reverse(i: int, j: int): while i < j: s[i], s[j] = s[j], s[i] i, j = i + 1, j - 1 i, n = 0, len(s) for j, c in enumerate(s): if c == " ": reverse(i, j - 1) i = j + 1 elif j == n - 1: reverse(i, j) reverse(0, n - 1)(code-box)

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; } } }(code-box)

class Solution { public: void reverseWords(vector<char>& s) { auto reverse = [&](int i, int j) { for (; i < j; ++i, --j) { swap(s[i], s[j]); } }; int n = s.size(); for (int 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); } };(code-box)

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

/** 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); }(code-box)