Problem

Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.

The input string does not contain leading or trailing spaces and the words are always separated by a single space.

Follow up

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

OR

Given a mutable string representation, can you perform this operation in-place?

Examples

Example 1:

1
2

Input: s = "the sky is blue"
Output: "blue is sky the"

Solution

Method 1 - Split and reverse the word order

This problem is pretty straightforward. We first split the string to words array, and then iterate through the array and add each element to a new string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
   public String reverseWords(String s) {
       if (s == null || s.length() == 0) {
           return "";
       }

       // split to words by space
       String[] arr = s.split(" ");
       StringBuilder sb = new StringBuilder();
       for (int i = arr.length - 1; i >= 0; --i) {
           if (!arr[i].equals("")) {
               sb.append(arr[i]).append(" ");
           }
       }
       return sb.length() == 0 ? "" : sb.substring(0, sb.length() - 1);
   }
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)

Method 2 - Reverse string and then reverse words individually

The solution can be attained by first reversing the string normally, and then just reversing each word.

1
2

initial: the house is blue
reverse: eulb si esuoh eht

Now reverse the word at its place

1
2
3

initial: the house is blue
reverse: eulb si esuoh eht
wanted : blue is house the

Another approach can be :

1
2

reverse the individual words in string
reverse the whole string.

Here is the example:

1
2
3

initial      : the house is blue
reverse words: eht esuoh si eulb
reverse      : blue is house the

Code

 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

class Solution {

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

		reverse(a, i, n - 1);

		reverse(s, 0, n - 1);
	}

	private void reverse(char[] a, int i, int j) {
		while (i < j) {
			char t = a[i];
			a[i++] = a[j];
			a[j--] = t;
		}
	}
}
 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

Complexity

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