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 <= 500word1andword2consist 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;
}
Input
word1 = "horse", word2 = "ros"
Output
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];
}
}
Input
word1 = "intention", word2 = "execution"
Output
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];
};
Input
word1 = "intention", word2 = "execution"
Output
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]
Input
word1 = "horse", word2 = "ros"
Output
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];
}
}
}
Input
word1 = "horse", word2 = "ros"
Output
3