An implementation of the edit distance problem using dynamic programming.

edit_distance.py

"""Edit Distance

An implementation of the edit distance problem using dynamic programming.
"""

import unittest

cache = {}

def edit_distance(first, second):
    """Find the edit distance between two strings"""

    if (first, second) in cache:
        return cache[(first, second)]

    if len(first) == len(second):
        distance = 0

        for i, _ in enumerate(first):
            if first[i] != second[i]:
                distance += 1

        cache[(first, second)] = distance
        return distance
    else:
        shorter, longer = sorted([first, second], key=len)
        min_distance = len(longer)

        for i, _ in enumerate(longer):
            before = longer[:i]
            after = longer[i + 1:]
            without_char = before + after
            distance = edit_distance(without_char, shorter)
            if distance < min_distance:
                min_distance = distance

        cache[(first, second)] = 1 + min_distance
        return 1 + min_distance

class Tests(unittest.TestCase):

    def test_same_string(self):
        """Compare string to itself"""

        first = "cat"
        distance = 0
        self.assertEqual(edit_distance(first, first), distance)

    def test_one_deletion(self):
        """Delete one character"""

        first = "cats"
        second = "cat"
        distance = 1
        self.assertEqual(edit_distance(first, second), distance)

    def test_one_medial_deletion(self):
        """Delete one character in the middle"""

        first = "cast"
        second = "cat"
        distance = 1
        self.assertEqual(edit_distance(first, second), distance)

    def test_two_deletions(self):
        """Delete two characters"""

        first = "chats"
        second = "cat"
        distance = 2
        self.assertEqual(edit_distance(first, second), distance)

    def test_deletions_replacement(self):
        """Delete two characters"""

        first = "chaps"
        second = "cat"
        distance = 3
        self.assertEqual(edit_distance(first, second), distance)

    def test_one_insertion(self):
        """Insert one character"""

        first = "cat"
        second = "cats"
        distance = 1
        self.assertEqual(edit_distance(first, second), distance)

    def test_two_insertions(self):
        """Insert two characters"""

        first = "cat"
        second = "chats"
        distance = 2
        self.assertEqual(edit_distance(first, second), distance)

    def test_replace_and_insert(self):
        """Replace and Insert"""

        first = "saturday"
        second = "sunday"
        distance = 3
        self.assertEqual(edit_distance(first, second), distance)

if __name__ == '__main__':
    unittest.main()