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:
- Insert a character
- Delete a character
- Replace a character
For example, the edit distance between “kitten” and “sitting” is 3, as we need to:
- Replace ‘k’ with ’s’
- Replace ’e’ with ‘i’
- 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, …
Continue Reading
Sign up or log in to access the full lesson and all 60 days of algorithm content.