Hackbright Code Challenges

One Edit Away?: Solution

One Edit Away?: Solution

Problem

One Edit Away?

Challenge

Medium

Concepts

Strings, Logic

Download

one-away-solution.zip


There are a few important realizations to make about the problem:

  • If the two words have lengths that are different by more than 1, there’s no possible single edit to fix them, so we can fail fast by checking length.

  • It will save us time to check for deletion, rather than inserting. For example, given the words “rasp” and “rap”, it’s easier to remove the “s” to see if it matches “rap” than to add every possible letter to “rap” to see if it matches “rasp”.

  • If the words have the same length, the only way they can be one away is by changing a letter, not by inserting/deleting. Conversely, if they have different lengths, the only way they can be one away is by inserting/deleting, not by changing.

  • It’s faster to just accept an error, rather than try every combination to make it work. We can allow one error for things to be one away. For example, when comparing “snap” and “snip”, we don’t need to try every replacement for the “a” in “snap” — we can just note that it didn’t match the “i” and, when we get to the end of checking all the characters, we can find that we only have one error, so they’re one away.

These realizations will allow us to make a solution with excellent runtime.

We’ll scan over both words, proceeding when we find matching characters. If the characters don’t match, we’ll do the following:

  • Note that there is an edit required. If we already found a required edit, they can’t be one away, so we can fail.

  • If the words are the same length, skip this character in both words. For example, when comparing “snap” and “snip”, when we hit the “a”/”i” difference, we’ll skip this and go to the “p” characters.

  • If the words are different length, we’ll skip to the next character in the longest word and continue checking. For example, when comparing “rap” and “rasp”, when we come to the 3rd character check, “p”/”s”, we’ll move to the next character in the longer word, the “p” in “rasp”, and keep checking. That matches the “p” in “rap”, and, since that’s the end of our loop, we’ve found the words are only one edit away.

This solution will be O(n), where n is the length of the longer word.

def one_away(w1, w2):
    """Given two strings, are they, at most, one edit away?"""

    # START SOLUTION

    # Strings length can only vary by, at most, one letter
    if abs(len(w1) - len(w2)) > 1:
        return False

    # Make sure w2 is the shorter string
    if len(w2) > len(w1):
        w1, w2 = w2, w1

    # Keep track of number of wrong letters
    wrong = 0

    # Loop over w1 with i and over w2 with j
    i = j = 0

    while j < len(w2):

        if w1[i] != w2[j]:

            # We found a wrong letter
            wrong += 1
            if wrong > 1:
                return False

            # We'll move to the next char in the longer string.
            i += 1

            # If same length, move the next char in shorter.
            # Otherwise, don't move in shorter string --- this
            # will cover the case of a added letter.
            if len(w1) == len(w2):
                j += 1

        else:
            # Both letters match; move to next letter in both
            i += 1
            j += 1

    return True