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.