Challenge: Edit Distance Problem
Let's solve the famous edit distance problem, otherwise known as the Levenshtein distance problem!
We'll cover the following
🗺️What is edit distance?
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.
The Levenshtein distance operations are the most famous operations we will be following for this example. These are the String
operations; each one of them has the same cost.
- Insertion
- Deletion
- Substitution
Problem statement
You are given two strings; write code to calculate how many minimum Levenshtein distance operations are required to convert one String
to another.
Input
The input is two words in the form of strings.
Output
The output is an integer of the minimum edit distance
Sample input
string str1 = "Tuesday";
string str2 = "Thursday";
Sample output
2
Do you know why output = 2?
First character “T” and last four characters “sday” are same. We basically need to convert “ue” to “hur”. This can be done using 2 operations i-e; Add
h
afterT
, Addr
afteru
.
The first character “T” and the last four characters “sday” are the same. We basically need to convert “ue” to “hur”. This can be done using two operations, i.e, add h
after T
, Add r
after u
.
Coding exercise
Take a close look and design a step-by-step algorithm first before jumping onto 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 hint and solution provided in the code tab. Good Luck!
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.