Skip to content

Instantly share code, notes, and snippets.

@joejag
Last active May 7, 2022 16:03
Show Gist options
  • Save joejag/b7b3e3e8828db11333cd327972a74b1d to your computer and use it in GitHub Desktop.
Save joejag/b7b3e3e8828db11333cd327972a74b1d to your computer and use it in GitHub Desktop.

Edit Distance

Write a function that returns whether two words are exactly "one edit" away using the following signature: bool OneEditApart(string s1, string s2); An edit is:

  • Inserting one character anywhere in the word (including at the beginning and end)
  • Removing one character
  • Replacing one character

Examples:

OneEditApart("cat", "dog") = false
OneEditApart("cat", "cats") = true
OneEditApart("cat", "cut") = true
OneEditApart("cat", "cast") = true
OneEditApart("cat", "at") = true
OneEditApart("cat", "act") = false
def one_edit_apart(s_one, s_two):
s1, s2 = sorted([s_one, s_two], key=len, reverse=True)
if len(s1) == len(s2):
for index, (l1, l2) in enumerate(zip(s1, s2)):
if l1 != l2:
return string_without(s1, index) == string_without(s2, index)
return True
if len(s1) == len(s2) + 1:
for index, (l1, l2) in enumerate(zip(s1, s2)):
if l1 != l2:
return string_without(s1, index) == s2
return True
return False
def string_without(s, index):
return s[:index] + s[index+1:]
import unittest
class TestSpiralMethods(unittest.TestCase):
def test_no_where_near(self):
self.assertFalse(one_edit_apart('cat', 'dog'))
def test_too_many_diffs(self):
self.assertFalse(one_edit_apart('cat', 'act'))
def test_same(self):
self.assertTrue(one_edit_apart('cat', 'cat'))
def test_one_letter_difference(self):
self.assertTrue(one_edit_apart('cat', 'car'))
def test_add_a_letter_at_the_end(self):
self.assertTrue(one_edit_apart('cat', 'cats'))
def test_add_a_letter_at_the_start(self):
self.assertTrue(one_edit_apart('rat', 'drat'))
def test_add_a_letter_in_the_middle(self):
self.assertTrue(one_edit_apart('cat', 'cart'))
def test_add_a_letter_in_the_middle_of_a_diff_string(self):
self.assertFalse(one_edit_apart('dog', 'cart'))
def test_add_two_letters(self):
self.assertFalse(one_edit_apart('cat', 'catss'))
unittest.main(exit=False)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment