Edit distance
Lesson 9 of 15 in Coddy's Dynamic Programming 101 course.
Edit distance, also known as Levenshtein distance, is a metric used to measure the difference between two strings. Specifically, it is the minimum number of operations needed to transform one string into another.
The possible operations are:
- Insertion: Insert a character into one of the strings
- Deletion: Delete a character from one of the strings
- Substitution: Replace a character in one of the strings with another character
Edit distance is widely used in fields such as natural language processing, computer vision, and bioinformatics.
Dynamic programming can be used to efficiently compute the edit distance between two strings.
Challenge
MediumWrite a Python function edit_distance that takes in two strings and returns the edit distance between them.
For example:
edit_distance("kitten", "sitting")should return 3edit_distance("intention", "execution")should return 5
Try it yourself
def edit_distance(str1, str2):
# Write code hereAll lessons in Dynamic Programming 101
3Dynamic programming algorithms
Longest common subsequenceKnapsack problemCoin change problemEdit distance