Edit Distance Problem
Let's solve the Edit Distance problem using Dynamic Programming.
Statement
Given two strings, str1 and str2, find the minimum edit distance required to convert str1 into str2. Minimum edit distance is the minimum number of insertions, deletions, or substitutions required to transform str1 into str2.
Note: This problem has a direct application in the autocorrect feature. It is also used in bioinformatics to quantify the similarity between two DNA sequences.
The visualization below shows all these operations. Each operation has a cost of one unit. Therefore, you want to find the minimum cost of converting str1 into str2. The following visualization also shows how different sequences of operations can entail different costs.
The alignment depiction in the above visualization is a hint toward the solution. You basically need to find an alignment between two strings that has the least cost. When characters match, there is no cost, but there is a cost of one unit when characters do not match (insertion, deletion, or substitution), or when a character is skipped (insertion or removal in str1) in either of the strings.
Constraints:
-
str1.length,str2.length str1andstr2are in the same case English letters
Examples
No. | str1 | str2 | Edit Distance |
1 | sunday | saturday | 3 |
2 | sam | sum | 1 |
Try it yourself
Implement your solution in the following playground.
import java.util.*;public class Main{public static int minEditDist(String str1, String str2) {return -1;}}
Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.
Hint: Use dynamic programming and see the magic.
Solution
We will first explore the naive recursive solution to this problem and then see how it can be ...