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

Edit Distance

Let's see if edit distance is a dynamic programming problem. We need to answer the two qualifying questions:

Does edit distance have overlapping subproblems?
Does edit distance have an "optimal substructure"?

In order to answer that, let's take a look at the naïve implementation.

def edit_distance(str1: str, str2: str) -> int:
    # 1st string is empty; distance is length of 2nd string
    if str1 == "":
        return len(str2)

    # 2nd string is empty; distance is length of 1st string
    if str2 == "":
        return len(str1)

    # last character in strings is the same;
    # distance is the same as the strings excluding
    # their last letters
    if str1[-1] == str2[-1]:
        return edit_distance(str1[:-1], str2[:-1])

    # last characters vary; distance is one more than
    # the smallest distance among the insert, delete, and
    # substitute operations
    return (
        1
        + min(
            edit_distance(str1, str2[:-1]),  # insert
            edit_distance(str1[:-1], str2),  # delete
            edit_distance(str1[:-1], str2[:-1]),  # substitute
        )
    )