Python: determine whether one string can be obtained by changing one character in the middle of another string

Question

This script solves a simple problem:

Input two strings differ one character or zero characters in length, return true if the following conditions are met:

1, They must start with same character and end with same character.

2, One string can be obtained by changing one character or zero characters in the middle of the other string (neither at the start nor end), here changing means replacing and inserting.

I have Google searched for several hours to find a solution and it was futile just as usual, I can't ask on stackoverflow.com because I am currently blocked from asking there because my questions are prone to be closed.

So after about half an hour I came up with a solution of my own:

def fuzzymatch(str1, str2):
    if abs(len(str1) - len(str2)) <= 1 and (str1[0], str1[-1]) == (str2[0], str2[-1]):
        longer = max(str1, str2, key=len)
        shorter = (str1 + str2).replace(longer, '')
        same = sum(''.join(longer[:i + 1]) in shorter for i in range(len(shorter)))
        if ''.join(longer[same + 1:]) in shorter:
            same += len(''.join(longer[same + 1:]))
        if abs(same - len(shorter)) <= 1 and len(str1) == len(str2):
            return True
        elif abs(same - len(longer)) <= 1:
            return True
    return False

I have tested it and confirmed its correctness:

In [2]: fuzzymatch('sample', 'ample')
Out[2]: False

In [3]: fuzzymatch('sample', 'sample')
Out[3]: True

In [4]: fuzzymatch('sample', 'sampley')
Out[4]: False

In [5]: fuzzymatch('sample', 'samply')
Out[5]: False

In [6]: fuzzymatch('sample', 'sammple')
Out[6]: True

In [7]: fuzzymatch('sample', 'sammmple')
Out[7]: False

In [8]: fuzzymatch('sample', 'simple')
Out[8]: True

In [9]: fuzzymatch('sample', 'siimple')
Out[9]: False

I know my approach is not very clean, that's why I am asking here, I want to know, what is a better approach, that gives the same result, is more efficient and with less complexity?

Answer 1

It would be good to include a docstring explaining the parameters and expected result. Best of all would be to include the unit-tests in doctest format:

def fuzzymatch(str1, str2):
    """
    Returns True if the two strings differ by only one letter (addition,
    removal or change) and that letter is not the first or last.
    >>> fuzzymatch('sample', 'ample')
    False

    >>> fuzzymatch('sample', 'sample')
    True

    >>> fuzzymatch('sample', 'sampley')
    False

    >>> fuzzymatch('sample', 'samply')
    False

    >>> fuzzymatch('sample', 'sammple')
    True

    >>> fuzzymatch('sample', 'sammmple')
    False

    >>> fuzzymatch('sample', 'simple')
    True

    >>> fuzzymatch('sample', 'siimple')
    False
    """

Now we can auto-test the function:

if __name__ == "__main__":
    import doctest
    doctest.testmod()

And we can add some more tests (for example, empty strings should return a value, rather than throwing an exception as they do right now).

---

It's often easier to deal with the simplest returns first, rather than having a long indented block where the reader is holding the condition in their head.

if str1[0] != str2[0] or str1[-1] != str2[-1]:
    return False

And we can simplify the longer/shorter stuff by simply swapping to make str1 always the longest:

if len(str1) < len(str2):
    str1, str2 = str2, str1

That is less work than concatenating the two and then finding and removing one of them.

This is a really inefficient way of finding the common suffix:

same = sum(''.join(str1[:i + 1]) in str2 for i in range(len(str2)))

String in string is a search, but we don't need a search, as we know where we expect to find the match. As well as inefficient, it's also obscure, since we have str.endswith() and str.startswith() at our disposal. A simpler version is

if len(str1) < len(str2):
    str1, str2 = str2, str1

# str1 is at least as long as str2 now
if len(str1) > len(str2) + 1:
    return False

for i in range(1, len(str2) - 1):
    if str2.startswith(str1[:i]) and str2.endswith(str1[i+1:]):
        return True

return False

We're still copying string slices around. To make it more efficient, we can look at a character at a time, and for this, I would create a helper function:

import itertools

def prefix_count(str1, str2):
    """
    Length of longest common prefix of str1 and str2

    >>> prefix_count('', '')
    0

    >>> prefix_count('a', '')
    0

    >>> prefix_count('a', 'b')
    0

    >>> prefix_count('ab', 'aa')
    1

    >>> prefix_count('aa', 'aa')
    2

    """
    return sum(1 for _ in itertools.takewhile(lambda x: x[0]==x[1], zip(str1, str2)))

We can now use that to find the common prefix forwards and backwards, and see if their length indicates that they meet with no more than 1 character of separation:

if len(str1) < len(str2):
    str1, str2 = str2, str1

# str1 is at least as long as str2 now
if len(str1) > len(str2) + 1:
    return False

if not str2 or str1[0] != str2[0] or str1[-1] != str2[-1]:
    return False

return prefix_count(str1, str2) + prefix_count(str1[::-1], str2[::-1]) + 1 >= len(str1)

---

Final modified version

import itertools

def prefix_count(str1, str2):
    """
    Length of longest common prefix of str1 and str2

    >>> prefix_count('', '')
    0

    >>> prefix_count('a', '')
    0

    >>> prefix_count('a', 'b')
    0

    >>> prefix_count('ab', 'aa')
    1

    >>> prefix_count('abc', 'aac')
    1

    >>> prefix_count('aa', 'aa')
    2

    """
    return sum(1 for _ in itertools.takewhile(lambda x: x[0]==x[1], zip(str1, str2)))


def fuzzymatch(str1, str2):
    """
    Returns True if the two strings differ by only one letter (addition,
    removal or change) and that letter is not the first or last.

    >>> fuzzymatch('', '')
    False

    >>> fuzzymatch('', 'a')
    False

    >>> fuzzymatch('aba', 'abca')
    True

    >>> fuzzymatch('aba', 'acba')
    True

    >>> fuzzymatch('acba', 'adba')
    True

    >>> fuzzymatch('sample', 'ample')
    False

    >>> fuzzymatch('sample', 'sample')
    True

    >>> fuzzymatch('sample', 'sampley')
    False

    >>> fuzzymatch('sample', 'samply')
    False

    >>> fuzzymatch('sample', 'sammple')
    True

    >>> fuzzymatch('sample', 'sammmple')
    False

    >>> fuzzymatch('sample', 'simple')
    True

    >>> fuzzymatch('sample', 'siimple')
    False

    >>> fuzzymatch('aabaa', 'aaaaaa')
    False
    """

    if len(str1) < len(str2):
        str1, str2 = str2, str1

    # str1 is at least as long as str2 now
    if len(str1) > len(str2) + 1:
        return False

    if not str2 or str1[0] != str2[0] or str1[-1] != str2[-1]:
        return False

    return prefix_count(str1, str2) + prefix_count(str1[::-1], str2[::-1]) + 1 >= len(str1)


if __name__ == "__main__":
    import doctest
    doctest.testmod()