Edit Distance Problem

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.