This lesson's interactive features are locked, please to keep using them

Slow Edit Distance

At Mappy we allow users to type the name of their destination in a search box. Unfortunately, it is very rare that users type the exact name of the place they want to go. The edit distance algorithm will allow us to provide the location of the local "McDonald's" when someone types "mc donalds".

Let's start by building the slow version of the edit distance algorithm.

Assignment

Complete the edit_distance function.

If the first string is empty, return the length of the second string; or if the second string is empty, return the length of the first string.
If the final characters of the two strings are the same, recursively return the result of edit_distance given the two strings with their last letters removed.
Otherwise, given that the last characters don't match, recursively calculate the edit_distance of each potential operation:
1. insert = the edit distance between the first string, and all but the last character of the second string.
2. delete = the edit distance between all but the last character of the first string, and the second string.
3. substitute = the edit distance between all but the last character of the first string, and all but the last character of the second string.
Return 1 plus the minimum edit distance among those three operations.