# Edit Distance Problem

Solve an interesting example taken from the SPOJ online contest based on strings and dynamic programming.

## 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`

.

- Insert
- Remove
- 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.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.