HiveBrain v1.2.0
Get Started
← Back to all entries
patternpythonMinor

Check if two strings are one 'edit' apart using Python

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
editareonetwousingpythoncheckstringsapart

Problem

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

Solution

All three cases are the same: you iterate over both string until there is a difference, you skip that difference and you check that the remaining of the strings are the same.

The only difference being how you skip the difference: you can store that in a dictionnary to also help short circuit in cases the length difference is 2 or more:

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"""

    skip_difference = {
        -1: lambda i: (i, i+1),  # Delete
        1: lambda i: (i+1, i),  # Add
        0: lambda i: (i+1, i+1),  # Modify
    }
    try:
        skip = skip_difference[len(first) - len(other)]
    except KeyError:
        return False  # More than 2 letters of difference

    for i, (l1, l2) in enumerate(zip(first, other)):
        if l1 != l2:
            i -= 1  # Go back to the previous couple of identical letters
            break

    # At this point, either there was no differences and we exhausted one word
    # and `i` indicates the last common letter or we found a difference and
    # got back to the last common letter. Skip that common letter and handle
    # the difference properly.
    remain_first, remain_other = skip(i + 1)
    return first[remain_first:] == other[remain_other:]

Code Snippets

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"""

    skip_difference = {
        -1: lambda i: (i, i+1),  # Delete
        1: lambda i: (i+1, i),  # Add
        0: lambda i: (i+1, i+1),  # Modify
    }
    try:
        skip = skip_difference[len(first) - len(other)]
    except KeyError:
        return False  # More than 2 letters of difference

    for i, (l1, l2) in enumerate(zip(first, other)):
        if l1 != l2:
            i -= 1  # Go back to the previous couple of identical letters
            break

    # At this point, either there was no differences and we exhausted one word
    # and `i` indicates the last common letter or we found a difference and
    # got back to the last common letter. Skip that common letter and handle
    # the difference properly.
    remain_first, remain_other = skip(i + 1)
    return first[remain_first:] == other[remain_other:]

Context

StackExchange Code Review Q#141603, answer score: 4

Revisions (0)

No revisions yet.