One Way Changes

Next up is writing a program which can compare two strings to see if they’ve been changed by having had one character removed, one extra character inserted, or one character replaced with a different character.

I tackled this by breaking it into three separate problems. I think the point of this question is to see whether you can decompose a problem into smaller steps and then see how you can glue them back together again.

First up is writing the function which can remove a character from one string and see if it matches the other string.

def removeChar(s1, s2):
    for n in range(len(s1)):
        if s2 == s1[:n] + s1[n+1:]
            return True
    return False

This is just walking through each character of the string and then using slicing techniques to construct new possible strings. If we match our second string, return True, otherwise just return False.

Next we need to check if a character was inserted into the first string. We could write a routine which adds each letter of the alphabet into each position of our first string, but that is needlessly fussy and would take a lot of time and complexity when there is a far better option. We’ve already got the string we’re trying to match against, so instead, let’s just reuse our removeChar() function and flip the two strings around. That way we’ll remove characters from our second string, and if the two strings match, we’ll know that a character was inserted.

def insertChar(s1, s2):
    return removeChar(s2, s1)

We then need to check if only one character is different in each of the strings. The easiest way to do this is just walk through one of the strings and compare it to the other one.

def replaceChar(s1, s2):
    if len(s1) != len(s2):
        return False

    oneChanged = False
    for n in range(len(s1)):
        if s1[n] != s2[n]:
            if oneChanged:
                return False
            oneChanged = True
    return oneChanged

Now that we’ve got all of our functions, we just glue them together.

def oneway(s1, s2):
    return insertChar(s1, s2) or removeChar(s1, s2) or replaceChar(s1, s2)

In terms of runtime complexity, we haven’t done anything super fancy here. We’re mostly just iterating through copies of one of the strings. The kicker though are the string slices. Those are making full copies of the string, which means we’re unfortunately at O(n²) time complexity. We might be able to use some other data structure for creating the slices, but unless there was some requirement for cutting that down, I think this solution is still sufficient.