Reverse Words in a String 2

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?

Examples

Example 1:

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

Java

Note: StringBuilder should be used to avoid creating too many Strings. If the string is very long, using String is not scalable since String is immutable and too many objects will be created and garbage collected.

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.

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

Now reverse the word at its place

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

Another approach can be :

reverse the individual words in string
reverse the whole string.

Here is the example:

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

Code

Java
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;
		}
	}
}

We can also write a separate function for swapping:

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)