Log In Sign Up
Day 36

Day 36: Edit Distance Problem

36/60 Days

Edit Distance Problem #

Welcome to Day 36 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore the Edit Distance Problem, a classic dynamic programming problem with applications in natural language processing, bioinformatics, and more.

What is the Edit Distance Problem? #

The Edit Distance Problem, also known as the Levenshtein Distance Problem, is about finding the minimum number of operations required to transform one string into another. The allowed operations are:

  1. Insert a character
  2. Delete a character
  3. Replace a character

For example, the edit distance between “kitten” and “sitting” is 3, as we need to:

  1. Replace ‘k’ with ’s’
  2. Replace ’e’ with ‘i’
  3. Insert ‘g’ at the end

Naive Recursive Approach #

Let’s start with a naive recursive implementation:

 1def edit_distance_naive(str1, str2, m, n):
 2    # If first string is empty, insert all characters of second string
 3    if m == 0:
 4        return n
 5
 6    # If second string is empty, remove all characters of first string
 7    if n == 0:
 8        return m
 9
10    # If last characters are same, …