JSFeeds: pub.scotch.io - The Ultimate Guide to JavaScript Algorithms: String Reversal

Wednesday, 23 January, 2019 UTC

The Ultimate Guide to JavaScript Algorithms: String Reversal

Summary

The string reversal algorithm is perhaps the most common JavaScript code challenge on the internet. In this article, we explore various string reversal techniques as a good number of string manipulation algorithms are dependent on ones ability to reverse a string.

Without further ado, let's get busy.

You should already have your development environment setup for this course. Update your cloned repository by running the command git pull. Inside the Beginner folder, navigate to the reverseString folder. Our work for this challenge will be done in here. Make sure to follow along in the index-START.js file.

The Challenge

Given a string of text, write an algorithm that returns the text received in a reversed format. E.g

reverseString('algorithms') // should return 'smhtirogla'

Algorithmic Thinking

The process here is quite simple and straight forward. Our function will receive only one parameter i.e the string to be reversed.

Next, we would have to manipulate the characters in this string logically in order to return the string in reverse.

Okay now! Let’s talk code.

Code Implementation

We will now explore four ways to solve this challenge below. They are:

Chaining in-built methods
Using a For-loop
Recursion Method
Using .reduce()

Chaining in-built methods

The **.split()** method is used to split a string into an array of characters. It receives one argument which specifies the separator that determines where every split occurs.

The .reverse() method reverses the order of the elements in an array.

The **.join()** method is used to combine the elements of an array into a string. It receives one argument which specifies the separator. When none is supplied, it defaults to a comma.

In the code snippet below we use these methods to create a one-line solution by chaining them in succession to split the received text into an array of characters, reverse the order of array’s elements and join the elements of the reversed array to produce the reversed text.

function reverseString(text) {
    return text.split("").reverse().join("")
}

Applying cutting-edge ES6 syntax, we can use the spread operator as shown below to tweak this solution a bit.

function reverseString(text) {
    return [...text].reverse().join('')
}

The spread operator … , like the .split() method will spread the characters of the string into array elements.

The For-Loop way

For loops are used to execute a piece of code as long as a condition is met. In the solution below, we use a decrementing for-loop to run through the string received and append each character to another variable in reverse order. See how this is done below:

function reverseString(text) {
    let result = ""

    for (let i = text.length - 1; i >= 0; i--) {
        result += text[i]
    }

    return result
}

Notice how we initialize the iterating variable i to the length of the string -1 . Since the index begins from zero, this gives us the index of the last character in the string. We simply append this last character to our result variable which is an empty string and continue the cycle until we are past the first character of the string i.e i is no longer greater than or equal to 0.

We can improve this implementation further as shown below,by using the for…of loop in ES6.

The for…of statement in JavaScript is used to execute a certain piece of code for each distinct item(property) of an iterable object.

We use it below to run through each character in the text received and append it to the beginning of a new variable result which we return on completion as it now holds the reversed string.

function reverseString(text){
    let result = "";

    for(let char of text){
        result = char + result
    }

    return result;
}

The Recursive Way

Recursion is a programming technique in which the intention is to reduce the problem into smaller instances of the same problem until it is completely solved. In the solution below, we write a function that does exactly so by calling itself repeatedly.

Within the function, we make use of the .substr() method in JavaScript to return a portion of the text received. It expects two parameters, one specifying the starting index and the other specifying the number of characters afterwards(optional).

function reverseString(text) {
    if (text === "") {
        return ""
    } else {
        return reverseString(text.substr(1)) + text[0]
    }
}

Above, we first run a check to see if we have an empty string. This is known as the terminal case i.e the case that ends the recursion. Without it the process would continue in an endless loop. That’s definitely not what we want.

When the text is empty, we return an empty string and the function terminates. When it’s not, we call the reverseString() function and a new string created by removing the first character of the text is passed in. It might be difficult to understand what is going on here. However, let’s try a more visual explanation using the table below:

In this table, we breakdown the process that occurs when we execute the recursive function on the string '``code``'.

reverseString('code')

STEPS	What is executed	What is returned
1	reverseString(‘code’)	‘c’
2	reverseString(‘ode’)	‘o’
3	reverseString(‘de’)	‘d’
4	reverseString(‘e’)	‘e’
END	reverseString(‘’)	“”

The recursive function we created continuously breaks down the problem into smaller chunks until it reaches the terminating condition. We continuously remove and return the first character on each call and re-execute the function on what is left. Notice that at the end we have successfully returned every character in the string and joining them together from the last call upwards, gives us the string in reverse i,e “edoc”. Bear in mind that the last string is empty.

Whewww!!! Please take time to properly understand this implementation as recursion is a very important yet quite complicated concept. You will find help for understanding this better at the end of the article.

Also, if you understand all we’ve done so far, and you don’t look like this right now, then you probably do not know how much of a superhero you are.

Let’s consider one final approach.

Using .reduce()

The .``**reduce()** method is used to execute a function on every member of an array until it results in a single output value. It receives the function to be executed and the initial value of the accumulator as arguments. The accumulator serves as a holder for the value returned in the last execution of the callback.

Let’s see how to do this:

function reverseString(text) {
    return text.split("").reduce((acc, char) => char + acc, '')
}

In the solution above, we split the text received into an array of characters and then we call the .reduce() method on the array which begins with an empty string as the initial value and accumulates each character in reverse until it has gone through all characters in the array. At this point, it returns the completely reversed string.

Using the ES6 spread operator, we have:

function reverseString(text) {
    return [...text].reduce((acc, char) => char + acc, '')
}

Testing

Testing Correctness with Jest

To run the tests on each implementation found above, run the following command in your terminal:

npm run test reverseString

Chaining in-built methods

Using a For-loop

Recursive Method

Using .reduce()

Can you believe it? Every implementation we considered passed all tests.

Now, let’s test performance and determine the fastest/ most optimal solution.

Testing Performance with JSPerf

Follow this link to compare the algorithms compared in this test. Here’s a screenshot of the results:

From the test carried out, the fastest solution we have considered is using the .reduce() method. Next, is the for-loop method which is only 6% slower and is a pretty close one. The slowest of them all is the method of chaining .split(), .reduce() and .join(59% slower).

Practical Application

This challenge though seemingly simple is one of the most popular coding interview questions ever. This is due to the fact that most languages do not have in-built methods for this functionality, hence it takes some level of understanding to get this done.

Conclusion

We have now set the stone rolling for the string manipulation challenges considered next in this section of this course.

We have seen various ways to reverse a string in JavaScript and have determined the **.reduce()** method to be the fastest. Interestingly, the approach of chaining .split(), .reverse() and .join() in succession is perhaps the most popular and direct implementation, yet the slowest performance-wise. In the articles that follow, we build on this knowledge in solving some slightly more complex challenges.

... more @ pub.scotch.io

pub.scotch.io