Code Challenge Practice IV

Xabier Casán
Nov 7 · 2 min read

oneEditAway

Let’s try to find solutions for the following task:

“There are three types of edits that can be performed on strings: insert a character, remove a character, or replace a character. Given two strings, write a function to check if they are one edit or zero edits away.”

We could use a “brute force” algorithm to solve this problem. We could check all possible strings that are one edit away by testing the removal of each character (and comparing), testing the replacement of each character (and comparing), and then testing the insertion of each possible character (and comparing).

That would be a very slow algorithm, so let’s not even think about implementing it.

Instead, this is a task where it’s helpful to think about the “meaning” of each of the operations:

1. Replacement: Consider two strings, such as “male” and “tale”, that are one replacement away. It means they are only different in one place.

2. Insertion: The strings “whole” and “hole” are one insertion away. This means that both strings are identical except for a shift at some point.

3. Removal: The strings “whole” and “hole” are also one removal away, since insertion and removal are opposite actions.

Let’s implement the algorithm now. Insertion and removal will be checked in one step, and replacement will be checked in another one.

We are going to decide which one to run depending on the length of the strings:

In terms of Big O notation, this algorithm takes O(n) time, where n is the length of the sorter string.

Since the functionality for oneEditReplace and oneEditInsert is very similar, we could merge them into one method:

In conclusion, both algorithms are valid. On the one hand, some may argue that the first approach is better as it’s clearer and easier to read. On the other hand, others may argue that the second approach is better, since it’s more compact and doesn’t duplicate code, which facilitates maintainability.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade