Edit Distance Problem

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 r and insert a and t before u. The minimum number of edits is 3.

Solution: Recursive approach

Let’s discuss the approach used in this solution.

• If the last characters of the two strings are the same, there is nothing much to do. Ignore the last characters and get the count for the remaining strings. Thus, we recur for lengths m-1 and n-1.
• Else (if the last characters are not the same), we consider all operations on str1, consider all three operations on the last character of the first string, recursively compute the minimum cost for all three operations, and take a minimum of three values.
  • Insert: Recur for m and n-1
  • Remove: Recur for m-1 and n
  • Replace: Recur for m-1 and n-1

Once the approach is clear, we can write some pseudocode that will also help us understand the recurrence relation.

• If str1[m] = str2[n]
  • editDist(str1, str2, m, n) = editDist(str1, str2, m-1, n-1)
• Else
  • editDist(str1, str2, m, n) = 1 + min{editDist(str1, str2, m-1, n) (Remove operation)
  • editDist(str1, str2, m, n-1) (Insert operation)
  • editDist(str1, str2, m-1, n-1) (Replace operation)

Instead of writing a recursive solution, we will write an iterative one because of overlapping subproblem. You can take an exercise to write a recursive solution. It would be very easy as we already discussed the pseudocode for the recursive approach above. Let’s move to the implementation now.