4
\$\begingroup\$

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)
\$\endgroup\$
2
  • \$\begingroup\$ Is it an implementation of Levenshtein distance? \$\endgroup\$ Sep 17 '16 at 12:25
  • 4
    \$\begingroup\$ You will probably be interested in how Peter Norvig solved a problem similar to this (a spelling corrector): norvig.com/spell-correct.html \$\endgroup\$
    – Caridorc
    Sep 17 '16 at 12:45
4
\$\begingroup\$

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:]
\$\endgroup\$
11
  • \$\begingroup\$ Wow, I understand this code and the algorithm. My question is what do I take alway from this answer so that I have a better chance of answering these sorts of questions on my own? Is the key understanding how my algorithm differs from yours and to practice transforming my code into what you have above? \$\endgroup\$ Sep 17 '16 at 11:53
  • 2
    \$\begingroup\$ There is no universal answer. For this question, the key is understanding that each operation is nearly the same so what is important is using the same part of the code to handle parts of the algorithm that are the same. And then figuring out an efficient way to handle the part that is different. \$\endgroup\$ Sep 17 '16 at 12:02
  • \$\begingroup\$ Actually, I just ran this and it failed for the test first = 'pales', other = 'pale', am I missing something? \$\endgroup\$ Sep 17 '16 at 12:46
  • \$\begingroup\$ I added the line if(i) == len(other) -1: return True after the for loop and it worked, not sure if that is a good way to handle that case. \$\endgroup\$ Sep 17 '16 at 13:00
  • 1
    \$\begingroup\$ @newToProgramming That how slicing works, an out-of-bounds slice will return the empty element. Anyway, this version should behave according to the requirements. The thing is that we need to account for words that are identical except for an extra last letter as well as words that have a difference in the middle. So we need a way to skip the last letter of the shorter word without skipping letters that are different. \$\endgroup\$ Sep 17 '16 at 13:34
2
\$\begingroup\$

You should better solve this algorithm in O(n) to pass the interview. So, in the case where you have a longer and a shorter string, skip the longest common prefix, skip one character of the longer string and compare the rest for equality.

Also, for use in real-life situations, in the case of equally long strings, you should return early as soon as there are 2 different characters.

Regarding the comments: you don't need to add any. The code is very clear in what it does, so every additional comment would disturb the reading flow.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Nothing to rename. But if you want to be meticulous: rename the function "is_one_way" doesn't mean anything for me, add a newline after the docstring first.line, and optionally, abbreviate num_different_chars to num_diff_chars. Remember this: the less you have code, the less you have bugs. I'm a quibbled! \$\endgroup\$ Sep 17 '16 at 12:18
  • \$\begingroup\$ @LaurentLAPORTE I, too, read it is_one_way but it's actually is_one_Away. Hope that makes sense now. \$\endgroup\$ Sep 17 '16 at 19:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.