Table of Contents

## Problem Statement

The problem **Edit Distance LeetCode Solution **states that you are given two strings `word1`

and `word2`

and you need to convert `word1`

into `word2`

in minimum operations. The operations that can be performed on the string are –

- Insert a character
- Delete a character
- Replace a character

### Examples

**Test Case 1 –**

**Input:** word1 – `horse`

word2 – `ros`

**Output:** 3

**Explanation:**

horse -> rorse (replace ‘h’ with ‘r’)

rorse -> rose (remove ‘r’)

rose -> ros (remove ‘e’)

**Test Case 2 –**

**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’)

## Approach

### Recursive Approach

- We need to traverse both the strings letter by letter either from left or right. Suppose we start from the right corner.
- Suppose
**n**is the length of`word1`

and**m**is the length of`word2`

. - Consider the last characters of the two strings. Following two cases can arise for these characters –
- If the last characters are the same, we can ignore these characters and recur for the rest of the strings i.e. recur for lengths
**(n-1)**and**(m-1)**. - If the last two characters do not match, then we can use one of the three mentioned operations and take the minimum of the three, plus one for the current operation, as the answer. The three operations will be
**Insert**– Recur for lengths**n**and**(m-1)****Delete**– Recur for lengths (**n-1)**and**m****Replace**– Recur for lengths (**n-1)**and**(m-1)**

- If the last characters are the same, we can ignore these characters and recur for the rest of the strings i.e. recur for lengths

### DP Approach

Clearly, the recursive approach is not an efficient one as in the worst case, the time complexity for the approach will be exponential. If you draw the recursion tree for some input, you will notice that there are several overlapping subproblems and a DP-based approach can be thought of for the problem. So we need to convert the recursive solution to a DP-based solution by storing the computed results in a temporary data structure.

- Let
`n`

be the length of the first string and`m`

be the length of the second word. We will create a DP matrix of size (n+1)*(m+1) to store the results. - Element
**dp[i][j]**will represent the minimum number of operations required to make the substring`word1[0....i)`

equal to the substring`word2[0....j]`

. - The first row of the matrix will represent the input when
`word1`

is an empty string and the first column of the matrix will represent the input when`word2`

is an empty string. So the base cases will be`dp[i][0] = i`

for**i in the range (0,n+1)**and`dp[0][j] = j`

for**j in the range (0,m+1)**. - Once the base cases are initialized, we can compute the rest of the elements in a way similar to the recursive approach.
- If the
`(i-1)th`

character of`word1`

matches`(j-1)th`

character of`word2`

,`dp[i][j] = dp[i-1][j-1]`

. - Else we will apply one of the following operations and take minimum of the three
**Insert**–`dp[i][j-1] + 1`

**Delete**–`dp[i-1][j] + 1`

**Replace**–`dp[i-1][j-1] + 1`

- If the
`Finally, we can return the value of`

`dp[n][m]`

.

### Code for Edit Distance LeetCode Solution

#### C++

class Solution { public: int minDistance(string word1, string word2) { int n = word1.size(), m = word2.size(); int ans = 0; vector<vector<int>> dp(n+1, vector<int>(m+1)); for(int i=0;i<=n;i++) dp[i][0] = i; for(int i=0;i<=m;i++) dp[0][i] = i; 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 dp[i][j] = 1 + min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])); } } return dp[n][m]; } };

#### JAVA

class Solution { public int min(int a, int b, int c){ if(a<=b && a<=c) return a; if(b<=a && b<=c) return b; return c; } public int minDistance(String word1, String word2) { int n = word1.length(), m = word2.length(); char first[] = word1.toCharArray(); char second[] = word2.toCharArray(); int dp[][] = new int[n+1][m+1]; for(int i=0;i<=n;i++) dp[i][0] = i; for(int i=0;i<=m;i++) dp[0][i] = i; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(first[i-1] == second[j-1]) dp[i][j] = dp[i-1][j-1]; else dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]); } } return dp[n][m]; } }

#### Python

class Solution(object): def minDistance(self, word1, word2): n = len(word1)+1 m = len(word2)+1 dp = [[0 for i in range(m)] for j in range(n)] for i in range(0,n): dp[i][0] = i for j in range(0,m): dp[0][j] = j for i in range(1,n): for j in range(1,m): if word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = 1+min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) # print(dp) return dp[n-1][m-1]

## Complexity Analysis for Edit Distance LeetCode Solution

### Time Complexity

We are traversing through a matrix of size **n*m** where **n** and **m** are lengths of the two strings. So the overall complexity for the algorithm is O(n*m).

### Space Complexity

We are creating a matrix of size **n*m** where **n** and **m** are lengths of the two strings to store the result for the sub-problems. So the space complexity for the algorithm is O(n*m).

Reference: https://en.wikipedia.org/wiki/Dynamic_programming