The code below is my solution in python 3 to exercise 1.5 in Cracking the Coding Interview. I would appreciate feedback on both the algorithm (improvements to space and time complexity) and/or coding style. I think the time and space complexity of the code below is \$O(n^{2})\$ and \$O(n)\$ respectively.
The exercise statement is as follows:
Given 2 Strings write a function to check if they are 1 edit away. There are three type of edits
1) Insert a character
2) Remove a character
3) Replace a character
I wrote the code in Python 3.5 and confirmed that it passed a small unit test. For this problem I am particularly interested in feedback on where in my code (if at all) I should include more comments.
import unittest
def is_one_away(first: str, other: str) -> bool:
"""Given two strings, check if they are one edit away. An edit can be any one of the following.
1) Inserting a character
2) Removing a character
3) Replacing a character"""
if len(first) < len(other):
first, other = other, first
if len(first) - len(other) > 1:
return False
elif len(first) - len(other) == 1:
for pos in range(len(first)):
if first[:pos] + first[pos+1:] == other:
return True
return False
else:
num_different_chars = sum(1 for pos in range(len(first)) if first[pos] != other[pos])
return num_different_chars < 2
class MyTest(unittest.TestCase):
def test_is_one_away(self):
self.assertEqual(is_one_away('pale', 'ale'), True)
self.assertEqual(is_one_away('pales', 'pale'), True)
self.assertEqual(is_one_away('pale', 'bale'), True)
self.assertEqual(is_one_away('pale', 'bake'), False)
self.assertEqual(is_one_away('ale', 'pale'), True)
self.assertEqual(is_one_away('aale', 'ale'), True)
self.assertEqual(is_one_away('aael', 'ale'), False)
self.assertEqual(is_one_away('motherinlaw', 'womanhitler'), False)
self.assertEqual(is_one_away('motherinlaw','motherinlow'), True)