Challenge: The Edit Distance Problem
Solve the famous edit distance/Levenshtein distance problem.
We'll cover the following
Edit distance is a metric to quantify how dissimilar two strings are to one another by counting the minimum number of operations required to transform one string into the other.
Edit distances find several applications in the real world. For example, it is used to figure out which word is misspelled in automatic spelling correction. In bioinformatics, it’s used to quantify the similarity between two DNA sequences.
Different definitions of an edit distance use different sets of string operations to determine the distance. The Levenshtein distance operations are the most famous: removal, insertion, or substitution of a character in the string. Levenshtein distance operations are what we will follow in this example.
Problem statement
Given two strings, write code to calculate how many minimum Levenshtein distance operations are needed to convert one into the other.
Input
Two strings.
Output
A number.
Sample input
str1 = "Sunday";
str2 = "Saturday";
Sample output
result = 3;
Coding challenge
First, take a close look at this problem and design a step-by-step algorithm before jumping to the implementation. This problem is designed for your practice, so try to solve it on your own first. If you get stuck, you can always refer to the solution provided in the solution section. Good luck!
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.