Search⌘ K
Home
Courses
Competitive Programming - Crack Your Coding Interview, C++

Edit Distance Problem

Explore the edit distance problem to understand how dynamic programming optimizes the calculation of minimum edits needed to transform one string into another. This lesson covers the operations of insert, remove, and replace, and explains the transition from a recursive to an iterative solution using a memoization table for efficiency.

We'll cover the following...

Problem statement

You are given two strings str1 and str2. The operations listed below can be performed on str1. Find the min number of edits (operations) required to convert str1 to str2.

  1. Insert
  2. Remove
  3. Replace

All the above operations are of equal cost.

Let us look at the following two examples:

  • We have two strings, str1 = cat and str2 = cut. To convert cat to cut, we just need to replace a with u and the minimum number of edits is 1.
  • We have two strings, str1 = sunday and str2 = saturday. The last 3 characters are the same, and we only need to replace un with atur. We need to replace n with
...