Grokking Dynamic Programming Interview/

...

/

Edit Distance Problem

Edit Distance Problem

Let's solve the Edit Distance problem using Dynamic Programming.

We'll cover the following...

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:

  • 1≤1 \leq str1.length, str2.length ≤500\leq 500
  • str1 and str2 are 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.

Press + to interact
Java
usercode > Main.java
import java.util.*;
public class Main{
    public static int minEditDist(String str1, String str2) {
        return -1;
    }
}
Edit Distance

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 improved using the Longest Common Substring dynamic programming pattern.

Naive approach

A naive approach is to process all the ...