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

- Insert a character
- Delete a character
- 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:

word1[pos] = word2[pos], we have to add nothing to our answer

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; }