From "hello world" to "world hello": Reversing the Words in a String

Today's algorithm is Reverse the Words in a String:

Given an input string, reverse the string word by word.

If the inputted string has whitespaces at the start or end, or extra spaces between words, the function should remove those spaces. For example, if you were given the string " hello world ", the function should output "world hello".

I like this algorithm because it combines a lot of different processes and tricks seen in many other problems. In this post, I'll discuss how I'll approach this problem, and then will code the solution in JavaScript.

Approaching the Problem

Strings themselves aren't very easy to work with in JavaScript. However, turning strings into arrays gives us a lot more to work with -- we can traverse arrays, delete elements, and reverse them, which is exactly what we'll need to do in this problem.

You can think of this problem as having a few distinct sections:

1. turn the string into an array using .split()
2. traverse the array, and delete any white spaces using `.splice()
3. reverse the array using two pointers
4. turn the array into a string using .join(), and return it

In the next section, I'll break down each of these parts.

Coding the Solution

First, we need to turn the string into an array. For this, we can use .split(). If we pass in a single blank space as the argument in .split(), that means the string will be split on blank spaces. For example:

const string = "happy birthday"
const arr = string.split(" ") // arr = ["happy", "birthday"]


We can store the split string into a variable called arr.

javascript
function reverseWords(s) {
const arr = s.split(" ")
//...
}


Now, the second thing we want to do is traverse the array arr and delete any white spaces. If there were leading or trailing whitespaces, or multiple spaces between words, then arr will have elements that are simply empty strings. Since our output shouldn't have these extra spaces, we'll need to delete them.

We can traverse arrays multiple ways, but for this I'll use a for loop. The for loop will go through each element in the array at index i. If the array at that index is an empty space, then we'll use .splice() to delete the element at that index. .splice() will take in two arguments: the index of the element to delete, which in this case is i, and the number of elements to delete, which in this case is 1.

The other important thing to do is to decrement, or decrease the count by 1, of i every time we delete an extra space from the array. This is an important step in case there are instances where there are two extra whitespaces in a row--if we don't decrement i, then we will skip over the second whitespace.

javascript
function reverseWords(s) {
const arr = s.split(" ")
for (let i = 0; i < arr.length; i++) {
if (arr[i] === "") {
arr.splice(i, 1)
i--
}
}
//...
}


The third step in our solution is to reverse the array. You can reverse arrays with .reverse(), but I personally like using two pointers. The reason I do this is because I think it's good practice to know how to reverse an array in place without using built-in methods--this kind of question comes up in programming interviews all the time.

So, for this problem, we'll use two pointers: one called left, which starts at index 0, and one called right, which starts at arr.length - 1, which is the last index in the array. We'll set up a while loop that will keep running as long as left is less than or equal to right. In the while loop, we'll swap the elements at the left and right pointers, and then will move the pointers closer to each other: left will increment, and right will decrement.

An important thing to keep in mind when swapping is to have a variable that temporarily stores the values of one of the points that will be swapped. We'll do this by setting a variable called temp equal to the array at the left pointer.

javascript
function reverseWords(s) {
const arr = s.split(" ")
for (let i = 0; i < arr.length; i++) {
if (arr[i] === "") {
arr.splice(i, 1)
i--
}
}
let left = 0
let right = arr.length - 1
while (left <= right) {
const temp = arr[left]
arr[left] = arr[right]
arr[right] = temp
left++
right--
}
//...
}


We now have an array of words in reverse order, without any extraneous whitespaces. We're almost done! The only thing left to do is to turn the array into a string, and return the string. We can turn the array into a string using .join(), and pass in a string with a single space: .join(" "). This means that the elements of the array will join together in a string, and each element will be separated by a single space.

javascript
function reverseWords(s) {
const arr = s.split(" ")
for (let i = 0; i < arr.length; i++) {
if (arr[i] === "") {
arr.splice(i, 1)
i--
}
}
let left = 0
let right = arr.length - 1
while (left <= right) {
const temp = arr[left]
arr[left] = arr[right]
arr[right] = temp
left++
right--
}
return arr.join(" ")
}


Please let me know in the comments if you have any questions or other ways of solving this problem!