The Ultimate Guide to JavaScript Algorithms - Lesson #9

JavaScript Algorithms: Hamming Distance

In this challenge we will come up with an algorithm to calculate the edit distance between two strings of equal length, also known as Hamming Distance.

The hamming distance between two strings of equal length is the number of positions at which these strings vary. In more technical terms, it is a measure of the minimum number of changes required to turn one string into another.

This is definitely an interesting one.

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 hammingDistance folder. Our work for this challenge will be done in here. Make sure to follow along in the index-START.js file.

Given two strings of equal length, calculate and return the the hamming distance. E.g

hammingDistance('rover', 'river') // should return 1

As clearly stipulated in the challenge statement, our function would receive two string arguments of equal length.

The strings received must be of equal length, hence it is reasonable for us to check that the strings passed in as arguments meet this requirement before any comparison occurs.

Next, We would need to compare every character in the first string with the character holding their corresponding position in the second string. This helps us identify the points where differences exist as it is the total count of these instances that gives us the hamming distance.

Bear in mind that lowercase a will differ from it's uppercase character A, hence all our comparisons must be done in a common case.

Lets do this!

In implementing the hamming distance algorithm, the algorithmic process is pretty much unchanging. Hence, we consider just one approach to solving this problem unlike in the previous challenges examined.

Using a for-loop In this approach, we use a for-loop as shown below to loop through every character of stringA while comparing each character with the character in their corresponding position for stringB.

function hammingDistance(stringA, stringB) {
    let result = 0

    if (stringA.length == stringB.length) {

        for (let i = 0; i < stringA.length; i++) {
            if (stringA++[++i].toLowerCase() != stringB++[++i].toLowerCase()) {
                result++
            }
        }

        return result

    } else {
        throw new Error('Strings do not have equal length')
    }
}

Notice that at the beginning, we add a check to ensure that the characters received are of equal length. We also convert all characters to lowercase before comparing them in order to avoid errors due to varying letter cases.

Testing Correctness with Jest To test the solution above, run the command below in your terminal:

npm run test hammingDistance

We get the following result:

All good! We passed all tests.

The hamming distance algorithm finds its application in telecommunication for error detection and correction. It is used to determine the number of distorted bits in a binary word as a way to estimate error. In the biological realm, it is also used to determine genetic distance.

In software engineering, it is a common code challenge for JavaScript interviews and could also come in handy for developing word games in the real world.

Unlike in our previous challenges, we have considered only one approach to solving this challenge in this article. This is due to the fact, that not many truly distinct solutions to this challenge exist. Hence, we do not carry out any bench-marking tests on JSPerf.

Do well to share your thoughts in the comment section below if you come up with a truly distinct solution for all to benefit from.

For further learning consider the resources below:

See you in the next one!✌🏿

Want to improve your coding and design skills?

I'm continually researching the best practices and tools for coding.
Join 50,000+ developers looking to make cool stuff.

We value your privacy. 1-click unsubscribe.

Comments

What did you think of the article? Let us know!
(these comments are powered by GitHub issues and use 0 trackers)