# Edit Distance

Companies:

## Problem Statement

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

1. Insert a character
2. Delete a character
3. Replace a character

## Sample Test Cases

```Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

```

## Problem Solution

We will be using Dynamic Programming Bottom-up approach.

We can maintain a DP table. Since, it is a bottom-up approach where do[I][j] gives you the minimum number of changes required when word1 is of size I and word2 is of size j.
So our answer will be dp[n][m] since word1 is of size n and word2 is of size m.

Now the base case is when any of word1 or word2 is empty. Then the answer is the length of word1 or word2 whichever is not empty.

Now after handling the base case we fill the DP table by using the three options (insert, delete or replace, any one of which will cost us 1 point). So we fill the dp by using the minimum of these three (insert, delete or replace points).

Now you have to figure out that
If:
Else:
dp[i – 1][j – 1] is for replace,
dp[i – 1][j] is for delete,
dp[i][j – 1] is for insert.
and add 1 + min of the above three cases to our answer.

## Complexity Analysis

Time Complexity: O( nm ) because we are traversing the matrix of size m x n (where m and n are the length of the strings).

Space Complexity: O( nm ) because we have to maintain the dp matrix of size m x n (where m and n are the length of the strings).

## Code Implementation

```#include<bits/stdc++.h>
using namespace std;

int minDistance(string word1, string word2) {
int n = word1.size(), m = word2.size();

int dp[n + 1][m + 1];

// if word2 is empty we have to remove all characters from word1
for(int i = 0; i <= n; i++) dp[i][0] = i;

// if word1 is empty we have to add all characters to word1
for(int j = 0; j <= m; j++) dp[0][j] = j;

// we have three cases replace, delete, insert
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
// 1 + min(replace, delete, insert)
dp[i][j] = 1 + min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1]));
}
}
}
return dp[n][m];
}
int main()
{
string a="horse";
string b="ros";

int x= minDistance(a,b);
cout<<x;
}```

Scroll to Top

### Full Stack Integrated Bootcamp Free Trial

• Please enter a number from 7000000000 to 9999999999.