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()