# Edit Distance

Posted: 18 Jul, 2020

Difficulty: Moderate

#### You are given two strings 'S' and 'T' of lengths 'N' and 'M' respectively. Find the "Edit Distance" between the strings.

#### Edit Distance of two strings is the minimum number of steps required to make one string equal to the other. In order to do so, you can perform the following three operations:

```
1. Delete a character
2. Replace a character with another one
3. Insert a character
```

##### Note:

```
Strings don't contain spaces in between.
```

##### Input format:

```
The first line of input contains the string 'S' of length 'N'.
The second line of the input contains the String 'T' of length 'M'.
```

##### Output format:

```
The only line of output prints the minimum "Edit Distance" between the strings.
```

##### Note:

```
You do not need to print anything; it has already been taken care of. Just implement the given functions.
```

##### Constraints:

```
0 <= N <= 10 ^ 3
0 <= M <= 10 ^ 3
Time Limit : 1sec
```

Approach 1

- We will write a recursive approach.
- The base case would be if the length of the first string is 0 then we need to add all the characters of the second string to the first string hence return the length of the second string. Similarly, if the length of the second string is 0 return length of the first string.
- Now the recurrence relation is as follows:
- If the last characters of two strings are not the same, try all operations and it will cost 1. Here
*i*is initially the last index of*s1*and*j*is initially the last index of*s2*and*f(i, j)*is the edit distance of*str1(0, i)*to*str2(0, j). str(i, j)*denotes the substring formed by taking the characters at index*i*through index*j*. *f(i, j) = 1 + min(f(i - 1, j), f(i, j - 1), f(i - 1, j - 1))*- Here the three recursive calls are for the insert, remove and replace respectively and s1, s2 will be parameters of all function calls. If the last characters of two strings are the same
*(s1[i] == s2[j])*then the relationship would be:*f(i, j) = f(i - 1, j - 1)*

- If the last characters of two strings are not the same, try all operations and it will cost 1. Here

Approach 2

- We will write a recursive approach and memoize it. So first make a 2D array of size
*(N + 1) x (M + 1)*where*N*and*M*are lengths of the two strings and fill it with -1. -1 means that we don’t know the answer for that state. - The base case would be if the length of the first string is 0 then we need to add all the characters of the second string to the first string hence return the length of the second string. Similarly, if the length of the second string is 0 return the length of the first string. Else check the value of the
*dp*array at index*i, j*. If it's not equal to*-1*, simply return its value. Otherwise, go the following step - The recurrence relation is as follows:
- If the last characters of two strings are not the same, try all operations and it will cost 1. Here
*i*is initially the last index of*s1*and*j*is initially the last index of*s2*.*f(i, j)*is the edit distance of*str1(0, i)*and*str2(0, j)*. *str(i, j)*denotes the substring formed by taking the characters at index*i*through index*j*.*f(i, j) = 1 + min(f(i - 1, j), f(i, j - 1), f(i - 1, j - 1))*- Here the three recursive calls are for the insert, remove and replace respectively and s1, s2 will be parameters of all function calls. If the last characters of two strings are the same
*(s1[i] == s2[j])*then the relationship would be:*f(i, j) = f(i - 1, j - 1)*

- If the last characters of two strings are not the same, try all operations and it will cost 1. Here
**Before returning the result, store it in the array at index i, j. This will save the overlapping subproblems.**

Approach 3

We will use the dynamic programming approach here and will have a 2-dimensional array, dp where

*dp[i][j]* stores the edit distance of the *(i+1)th* length substring of *str1* and *(j+1)th* length substring of *str2* starting from index *0*

The base case would be when the size of first-string is 0 then edit distance will be equal to the size of other string i.e when *i = 0* then *dp[i][j] = j* and similarly vice versa, so if *j = 0* then *dp[i][j] = i.*

Now we will use our recurrence relation

```
// If str1[i - 1] == str2[j - 1]
dp[i][j] = dp[i-1][j-1]
// Otherwise
dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])
```