Question

LeetCode Link | 151. Reverse Words In a String | Medium

Given an input string 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 at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Constrains

  • 1 <= s.length <= 10^4
  • s contains English letters (upper-case and lower-case), digits, and spaces ' '.
  • There is at least one word in s.

Examples

Example 1

Input: s = “the sky is blue”
Output: “blue is sky the”

Example 2

Input: s = “ hello world “
Output: “world hello”
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3

Input: s = “a good example”
Output: “example good a”
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Solution Approach

Method: Two-pointers

Constrains

  • None

This method does not have any limitations.

Concept Explanation

This question can be solve using split() function to separate words, then define a new string, and finally concatenate the words in reverse order, turning this problem into a trivial one, which loses its intended challenge.

1
2
3
function reverseWords(s: string): string {
   return s.trim().split(/\s+/).reverse().join(' '); 
};

Let’s try not to use auxiliary space, and keep the space complexity to O(1). Once auxiliary space is ruled out, we must then be focused on manipulating the original string itself.

Consider this: if we reverse the entire string, the order of the words would definitely be reversed, but the words themselves would also be reversed. So, if we then reverse each word individually, wouldn’t the words be oriented correctly?

Thus, the solution approach is as follows:

  1. Remove extra spaces
  2. Reverse the entire string
  3. Reverse back each word individually

For example, the string as: " the sky is blue ":

  1. Remove extra spaces: "the sky is blue"
  2. Reverse the entire string: "eulb si yks eht"
  3. Reverse word: "blue is sky the"

In this way, we completely reverse the world only.

1. Remove Extra Spaces

Concept similar as the question 27. Remove Element, where in this question we are gonna remove space instead of an element. By using fast & slow pointer, we can keep time complexity in O(n) instead of O(n2). For more detail, check the solution approach for question 27.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function removeExSpace(arrStr: string[]): void {
  let slow: number = 0;
  let fast: number = 0;
  while (fast < arrStr.length) {
    if (arrStr[fast] != ' ') {
    	// Add space at font if not the first word
    	if (slow != 0) arrStr[slow++] = ' ';
    	// Filling word in place
    	while (fast < arrStr.length && arrStr[fast] != ' ') {
     		arrStr[slow++] = arrStr[fast++];
    	}
  	}
  	fast++;
  }
  // Update arr length
  arrStr.length = slow;
};

2. Reverse the entire string

This is implemented on question 344. Reverse String which also been used on question 541. Reverse String II. We can add some new parameter that allows function reverse string only in a specific range which will also been used for the word reverse later. For more detail, check the solution approach for question 344 and question 541 if you want.

1
2
3
4
5
6
7
function reverseString(arrStr: string[], start: number, end: number): void {
  while (start < end) {
    [arrStr[start], arrStr[end]] = [arrStr[end], arrStr[start]];
    start++;
    end--;
  }
};

3. Reverse word

The only difference between reverse a word or entire sentence is the range of the index. We can find this range by checking wether a space we reached since no extra space is in the string now.

1
2
3
4
5
6
7
8
9
let wordStart: number = 0;
for (let i = 0; i <= arr.length; i++) {
  // When index reach end of word
  if (arr[i] === ' ' || i === arr.length) {
    reverseString(arr, wordStart, i - 1);
    // Set start index to next word
    wordStart = i + 1;
  }
}

Code

  • Time complexity: O(n)
  • Space complexity: O(1)

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
function reverseWords(s: string): string {
    // This function remove extra space
    function removeExSpace(arrStr: string[]): void {
        let slow: number = 0;
        let fast: number = 0;
        while (fast < arrStr.length) {
            if (arrStr[fast] != ' ') {
                // Add space at font if not the first word
                if (slow != 0) arrStr[slow++] = ' ';
                // Filling word in place
                while (fast < arrStr.length && arrStr[fast] != ' ') {
                    arrStr[slow++] = arrStr[fast++];
                }
            }
            fast++;
        }
        // Update arr length
        arrStr.length = slow;
    }

    // This function reverse string from given index range
    function reverseString(arrStr: string[], start: number, end: number): void {
        while (start < end) {
            [arrStr[start], arrStr[end]] = [arrStr[end], arrStr[start]];
            start++;
            end--;
        }
    }

    let arr: string[] = s.split('');
    // Remove extra space
    removeExSpace(arr);
    // Reverse whole sentence
    reverseString(arr, 0, arr.length - 1);

    // Reverse back words
    let wordStart: number = 0;
    for (let i = 0; i <= arr.length; i++) {
        // When index reach end of word
        if (arr[i] === ' ' || i === arr.length) {
            reverseString(arr, wordStart, i - 1);
            // Set start index to next word
            wordStart = i + 1;
        }
    }

    return arr.join('');
};

Conclusion

This problem can be seen as a comprehensive test of various string manipulations. It use serval function that we implement in previous question. The trim and split function makes this question relatively easy for sctipt language, but remember to shows a more deep solution as we discover above during interview since this is not a test that test you how to use a library function.