Challenge: The Edit Distance Problem
In this lesson, we will see another classic string related dynamic programming problem.
We'll cover the following
Problem statement
Given two strings, str1
and str2
, find the minimum number of operations required to be operated on str1
to convert it into str2
. There can be three kinds of operations: i) insertion of a character at some specific position, ii) deletion of a character at some specific position, or iii) changing a character at some specific position into some other character. The visualization below shows all these operations. Each operation has a cost of one unit. Thus, 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.
Note: This problem has a direct application in the autocorrect feature.
Get hands-on with 1400+ tech skills courses.