Leetcode 150 | Day 8: Reverse Words In a String - Naive vs. Optimized

Problem Description and Constraints

Leetcode 151 asks us to take a string of words and reverse them. To be clear we are not reversing the letters within each word, only the order of the words themselves.

I'll use Example 1 from Leetcode to illustrate.

Example 1:

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

Additionally our input string may have leading and/or trailing white space. The string we return should have this leading and trailing white space removed if it exists. **See Example 2

Example 2:

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

Throughout both approaches (Naive and Optimized) we will use the Example 2 from above.

Input: s = "   the sky is blue   "

Approach 1: Naive (Trim + Split + Regex + Join)

Below you can see the naive solution in its entirety. As you can see it's entirely possible to solve this problem in only one line of code.

Recall from Leetcode 88 Day 1, that brevity does now always mean a more efficient solution. But in this case, I am of the opinion that readability is benefited greatly by brevity.

/** 
* @param {string} s 
* @return {string} 
*/ 

var reverseWords = function(s) { 
     return s.trim().split(/\s+/).reverse().join(' '); 
};

Lets break this down line by line.

function reverseWords(s) {
}

• This is simply our function header. We are writing a function declaration. This function expression accepts a single parameter of s - *our input string.

The body of the function has 1 line:

s.trim().split(/\s+/).reverse().join(' '); 

JavaScript has several built in methods that can be called on strings. JavaScript allows us to chain these methods together, calling each one in succession.

Starting with:

s.trim()

This method strips leading and trailing whitespace from s

So:

Input: s = "   the sky is blue   "

Becomes:

Input: s = "the sky is blue"

Next we have:

.split(/\s+/)

.split() splits the string into a new array of words. And does so by using a regular expression (regex) as the delimiter.

/ /

• is required for all regular expressions. It's how JavaScript knows to treat what is between them as a regex object and not a string or some other data type.

\s

• s on its own is just the literal letter s. However, if we proceed s with \, the \ acts as an escape character - which changes the meaning, and now s means ***whitespace.

So, \s is an instruction that looks for whitespace. The inclusion of the + is a quantifier that means 1 or more.

What we have in the end:

\s+ is an instruction that tells JavaScript to look for 1 or more whitespace characters and split the string where it finds it. This has the effect of breaking the string up into its individual words and storing those words as elements in the array that it creates.

In the image above, the regex formula identifies the white space (represented by the red blocks at indexes 3, 7 and 10 and stores only the words as elements in the resulting array).

.reverse()

This method reverses the order of the elements in the array created by .split() and it does so in place, no additional data structures are created.

Lastly, we have:

.join(' ')

We do not want to return the array of reversed words. We want to return a string, the same data type we started with. To do this, we leverage .join(), which takes the array of reversed words and joins them back together again, as a string,

Complexity

• This solution has an O(n) time complexity. The reason for this is that trim(), split(), reverse(), and join() all walk through the string or array once, from start to finish. Even though we have multiple linear passes through our data, this is still linear overall.
• Space complexity here is also O(n). The reason for this is that .split() creates a new array, and that array will scale with input size.

Approach 2: Optimized (Manual Index Manipulation)

Here is the solution for approach 2 in its entirety.

function reverseWords(s) {
  const chars = s.split('');
  
  const reverse = (arr, left, right) => {
    while (left < right) {
      [arr[left], arr[right]] = [arr[right], arr[left]];
      left++;
      right--;
    }
  };  

  // Step 1: reverse the whole array
  reverse(chars, 0, chars.length - 1);  

  // Step 2: reverse each word back to correct letter order
  let start = 0;
  for (let i = 0; i <= chars.length; i++) {
    if (i === chars.length || chars[i] === ' ') {
      reverse(chars, start, i - 1);
      start = i + 1;
    }
  }  

  // Step 3: clean up spaces (trim ends)
  return chars.join('').trim().replace(/\s+/g, ' ');
}

Starting at the top, we have:

const chars = s.split('');

We are calling the .split() and pass through '' (empty string, no space) as the argument.

Just like in Approach 1, .split() breaks up the input string s into an array. In this case though, we get a character array. Each index within the character array will hold one character, including white space.

Why convert it to an array?

Because strings are immutable. Using strings to achieve our goal of reversing a string of words would require many intermediate strings be created and in JS engines, this could result in an O(n^2) time complexity.

However, arrays are mutable. This means we can do all of our necessary reversals in place - only one additional data structure required.

Next, we need that reverse helper.

const reverse = (arr, left, right) => {
    while (left < right) {
      [arr[left], arr[right]] = [arr[right], arr[left]];
      left++;
      right--;
    }
  };

This helper uses a standard two pointer approach. Each pointer's initial position (left and right), as well as the array we created with the split() method are passed in as arguments.

We start by entering a while loop. The condition of the while loop is as follows:

while (left < right)

We will have one pointer start at either end of the chars array. Each pointer will continue to take one step towards the middle of the array, on each loop iteration while the condition is still true. This is to ensure that the pointers do not cross.

While the condition evaluates to true, we will:

[arr[left], arr[right]] = [arr[right], arr[left]];

This line is using destructuring to swap the values at each index. We could also write this line like this

const temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;

This would achieve the same end result. But destructuring removes repetition, the need for temp variables, and is generally cleaner and easier to read.

Lastly we increment the left pointer one position to the right, and the right pointer one position to the left.

Step 1: Reverse the entire array

reverse(chars, 0, chars.length - 1);

We call our helper function and pass in the following arguments:

• chars - our array we just created from our original input string s
• 0 - The starting index for our left pointer
• chars.length - 1 - The starting index for our right pointer which is the furthest right index in our array.

What we have now is an array where every character has been reversed. So for example, if our input string s contained the string:

const s = '   the sky is blue   ';

Then our chars array, after calling our helper function reverse would now contain:

const chars = [' ', ' ', ' ', 'e', 'u', 'l', 'b', ' ', 's', 'i', ' ', 'y', 'k', 's', ' ', 'e', 'h', 't', ' ', ' ', ' ']

This still isn't quite right. The words themselves are in the correct reversed order, but the words themselves also read backwards.

The next step is to fix this.

Step 2: Reverse Each Word to Fix Letter Order

let start = 0;

  for (let i = 0; i <= chars.length; i++) {
    if (i === chars.length || chars[i] === ' ') {
      reverse(chars, start, i - 1);
      start = i + 1;
    }
  }

To help make this condition clear:

if (i === chars.length || chars[i] === ' ')

I am including and will be referencing the following visual.

This condition is checking for 2 things to be able to determine the end of a word:

1. Is the current character a space? This would be true at index positions 4, 7, and 11.
2. Have we gone past the end of the array itself? This is important as we can see the final word ends at index position 14 - the end of the array. There is not a space after the last word, so we need an alternate way of being able to detect the final word. Determining whether we have gone past the end of the array works well for this.

Every time we hit either of the two conditions we have encountered the end of a word, and we need to again call the reverse() helper so that we can put each letter in the word back in the correct order.

reverse(chars, start, i - 1);

Again, our arguments being passed in are:

• chars: Our input array
• start: We start at the beginning with index 0.
• i - 1: We use i - 1 because this point corresponds with the final char in a given word.

By calling reverse()on each word individually, we are keeping the reverse order of the words while correcting the order of each letter within each word.

So for, example prior to Step 2, our array looked like this

And once we've completed Step 2, our array now looks like this:

At this stage we have an array with precisely what we need. However, the problem asks us to:

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

Step 3: Join back into a String and Cleanup

So, the final step is to convert this back to a string and remove any leading or trailing white space.

We do that with this line of code

return chars.join('').trim().replace(/\s+/g, ' ');

chars.join() will take all of the elements in ourchars array and reform a string from them

.trim() removes all of the leading and trailing white space

.replace(/\s+/g, ' ') ensures that the whitespace between words is limited to a single white space. Notice this is nearly identical to the regular expression we used in the naive solution. The inclusion of g means take all instances of multiple whitespace in a row between words, and replace it with a single whitespace - g is a global flag.

And all of these functions can just be chained one onto the next, just like in our naive solution.

Conclusion

Surface level time complexity is the same for both approaches, O(n). So what really makes Approach 2 optimized?

We have to look a bit beyond space and time complexity on this one. While its true that both are O(n), lets remember that when determining time complexity, its standard to drop constants. Approach 2 reduces the number of passes over the data - which to be fair, may or may not always make for a meaningful difference.

In the naive solution there are at least four full passes:
* .trim()
* .split()
* .reverse()
* .join()

Whereas, with our optimized approach we have 2 major passes, one for reversing the entire array and another to reverse each word, and one cleanup pass.

Additionally, using regex as the delimiter when calling .split() is a costly use of regex. Regex is an incredibly powerful tool, but also has the potential to become so slow it can freeze a process. Instead, in Approach 2 we use regex purely to clean up additional unwanted whitespace between words - this is a relatively cheap use of regex.

Whether the optimized approach is the correct approach in this case may depend on the size of your dataset. The part of me that really appreciates readability certainly leans heavily towards Approach 1 (naive). However, the use of regex here and the extra linear passes can be costly and may limit this approaches strengths once it starts trying to handle larger datasets.

The optimized approach feels verbose - especially when a single line of code can get the job done.

This Leetcode is a great example in analyzing trade-offs - showing us that there really isn't one ideal way to approach problem solving. Choosing one way, improves one aspect while also complicating another. The same is true for most any approach. The key is to determine whether the improvement outweighs the complication for your use case.