One Edit Away

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.

Solution 1

We need to write two algorithms: one to identify a replacement, and another to identify an insert. The removal operation will look like an insert operation if we reverse the order of the strings.

Let’s start with the replacement algorithm. We can solve this problem by iterating through the two arrays at the same time, and comparing each element.

def one_replacement_away(string_1, string_2):
    edits = 0

    for i in range(len(string_1)):
        if(string_1[i] != string_2[i]):
            if(edits > 0):
                return False
            edits += 1

    return True

Now, let’s build the insert algorithm. Here, we will use two indices to keep track of where we are in each array. When the values do not match, we will increment the larger array (but not the smaller array). When the values match, we will increment both arrays. Eventually we will reach the end of the larger array. If we have also reached the end of the smaller array, the strings are one insert apart.

def one_insert_away(string_1, string_2):
    i = j = 0

    while(j < len(string_2)):
        if(string_1[i] == string_2[j]):
            i += 1
            j += 1

        else:
            j += 1

    if(i == len(string_1)):
        return True
    else:
        return False

To solve the original problem, we need to stitch these two algorithms together in a single function.

def one_edit_away(string_1, string_2):
    if(len(string_1) == len(string_2)):
        return one_replacement_away(string_1, string_2)
    elif(len(string_1) == len(string_2) - 1):
        return one_insert_away(string_1, string_2)
    elif(len(string_2) == len(string_1) - 1):
        return one_insert_away(string_2, string_1)
    else:
        return False

The runtime of this algorithm is \(O(n)\), where \(n\) is the length of the shorter string.