## Algorithm

Problem Name: 72. Edit Distance

Given two strings `word1` and `word2`, return the minimum number of operations required to convert `word1` to `word2`.

You have the following three operations permitted on a word:

• Insert a character
• Delete a character
• Replace a character

Example 1:

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

Example 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')```

Constraints:

• `0 <= word1.length, word2.length <= 500`
• `word1` and `word2` consist of lowercase English letters.
` `

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
int minDistance(char* word1, char* word2) {
int rowsz, colsz, row, col, *dp, k;

rowsz = strlen(word1);
colsz = strlen(word2);

dp = malloc((rowsz + 1) * (colsz + 1) * sizeof(int));
//assert(dp);
#define IDX(ROW, COL) ((ROW + 1) * (colsz + 1) + (COL + 1))

dp[0] = 0;
for (row = 0; row  <  rowsz; row ++) {
dp[IDX(row, -1)] = row + 1;
}
for (col = 0; col  <  colsz; col ++) {
dp[IDX(-1, col)] = col + 1;
}

for (row = 0; row  <  rowsz; row ++) {
for (col = 0; col  <  colsz; col ++) {
k = dp[IDX(row - 1, col - 1)];
if (word1[row] != word2[col]) {
k = k  <  dp[IDX(row - 1, col)] ? k : dp[IDX(row - 1, col)];
k = k < dp[IDX(row, col - 1)] ? k : dp[IDX(row, col - 1)];
k += 1;
}
dp[IDX(row, col)] = k;
}
}

k = dp[IDX(rowsz - 1, colsz - 1)];
free(dp);

return k;
}
``````
Copy The Code &

Input

cmd
word1 = "horse", word2 = "ros"

Output

cmd
3

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int minDistance(String word1, String word2) {
int n = word1.length();
int m = word2.length();
if (n * m == 0) {
return n + m;
}
int[][] dp = new int[n + 1][m + 1];
for (int i = 0; i  < = n; i++) {
dp[i][0] = i;
}
for (int j = 0; j  < = m; j++) {
dp[0][j] = j;
}
for (int i = 1; i  < = n; i++) {
for (int j = 1; j  < = m; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
}
}
}
return dp[n][m];
}
}
``````
Copy The Code &

Input

cmd
word1 = "intention", word2 = "execution"

Output

cmd
5

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const minDistance = function(word1, word2) {
let m = word1.length, n = word2.length;
const dp = Array.from({length: m + 1}, ()=> new Array(n+ 1).fill(0))
for (let i = 1; i  < = m; i++) {
dp[i][0] = i;
}
for (let j = 1; j  < = n; j++) {
dp[0][j] = j;
}
for (let i = 1; i  < = m; i++) {
for (let j = 1; j  < = n; j++) {
if (word1[i - 1] === word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
}
}
}
return dp[m][n];
};
``````
Copy The Code &

Input

cmd
word1 = "intention", word2 = "execution"

Output

cmd
5

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def minDistance(self, w1: str, w2: str) -> int:
dp = [[0] * (len(w2) + 1) for i in range(len(w1) + 1)]
for i in range(len(w1) + 1):
for j in range(len(w2) + 1):
if not (i and j):
dp[i][j] = i or j
elif w1[i - 1] == w2[j - 1]:
dp[i][j] += dp[i - 1][j - 1]
else:
dp[i][j] += min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
return dp[-1][-1]
``````
Copy The Code &

Input

cmd
word1 = "horse", word2 = "ros"

Output

cmd
3

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
using System;

namespace LeetCode
{
public class _072_EditDistance
{
public int MinDistance(string word1, string word2)
{
int size1 = word1.Length + 1, size2 = word2.Length + 1;
if (size2 > size1) { return MinDistance(word2, word1); }

var path = new int[size2];

int i, j, upper_left, upper;
for (i = 0; i  <  size2; i++) { path[i] = i; }

for (i = 1; i  <  size1; i++)
{
upper_left = path[0];
path[0] = i;

for (j = 1; j  <  size2; j++)
{
upper = path[j];

if (word1[i - 1] == word2[j - 1]) { path[j] = upper_left; }
else
{
path[j] = Math.Min(upper_left, Math.Min(path[j], path[j - 1])) + 1;
}

upper_left = upper;
}
}

return path[size2 - 1];
}
}
}
``````
Copy The Code &

Input

cmd
word1 = "horse", word2 = "ros"

Output

cmd
3