# Leetcode Edit Distance problem solution

Apr 22, 2023

In the Leetcode Edit Distance problem solution 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.

## Solution in C Programming

``````#include <string.h>

int min(int a, int b, int c){
int m = a;
if(a > b){
m = b;
}
if(m > c){
return c;
}else{
return m;
}
}

int minDistance(char * word1, char * word2){
int l1 = strlen(word1);
int l2 = strlen(word2);
char *w1 = (char *)malloc((l1+3)*sizeof(char));
char *w2 = (char *)malloc((l2+3)*sizeof(char));

for(int i=0;i<=strlen(word1)+1;i++){
if(i==0){
w1[i] = '#';
}else if(i<=strlen(word1)){
w1[i] = word1[i-1];
}else{
w1[i] = '\0';
}
}

for(int i=0;i<=strlen(word2)+1;i++){
if(i==0){
w2[i] = '#';
}else if(i<=strlen(word2)){
w2[i] = word2[i-1];
}else{
w2[i] = '\0';
}
}
// printf("%s\n", w1);
// printf("%s\n", w2);
int m[l2+1][l1+1];
for(int i=0;i<strlen(w2);i++){
m[i][0] = i;
}
for(int j=0;j<strlen(w1);j++){
m[0][j] = j;
}

for(int i=1;i<=l2;i++){
for(int j=1;j<=l1;j++){
m[i][j] = min(m[i-1][j]+1, m[i][j-1]+1, m[i-1][j-1]+(int)(w1[j]!=w2[i]));
}
}

// for(int i=0;i<=l2;i++){
//     for(int j=0;j<=l1;j++){
//         printf("%d ",m[i][j]);
//     }
//     printf("\n");
// }

return m[l2][l1];
}``````

## Solution in C++ Programming

``````class Solution
{
public:
int minDistance(string word1, string word2)
{
int n = word1.size();
int m = word2.size();
int dp[n+1][m+1];

// Initialize inserting i times option
for (int i = 0; i<=m; i++)
dp[0][i]=i;

// Initialize removing i times option
for (int i = 0; i<=n; i++)
dp[i][0]=i;

for (int i = 1; i<=n; i++)
{
for (int j = 1; j<=m; j++)
{
// chusing the lowest count to get to i,j
// keeping if characters are the same
int count = dp[i-1][j-1];
// if not the same replacing option path => count increase
if (word1[i-1] != word2[j-1])
count++;
// compare to getting to i,j by removing option path
count = min(dp[i-1][j]+1,count);
// compare to getting to i,j by inserting option path
count = min(dp[i][j-1]+1,count);
dp[i][j] = count;
}
}
return dp[n][m];
}
};``````

## Solution in Java Programming

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

## Solution in Python Programming

``````class Solution:
def minDistance(self, word1, word2):
memo = {}
def edit(word1, word2):
if (word1, word2) in memo:
return memo[word1, word2]
if len(word1) == 0 or len(word2) == 0:
return len(word1) + len(word2)
if word1[0] == word2[0]:
memo[word1, word2] = edit(word1[1:], word2[1:])
return memo[word1, word2]
memo[word1, word2] = min(1 + edit(word1[1:], word2),
1 + edit(word1, word2[1:]),
1 + edit(word1[1:], word2[1:]))
return memo[word1, word2]
return edit(word1, word2)``````

## Solution in C# Programming

``````public class Solution {

public int calculate(string w1, string w2, int m, int n, int[,] dp)
{
//if m string ended before that means m has to be added with 1 to be equal to n
if(m == -1)
return n+1;
if(n == -1)
return m+1;

//return stored value
if(dp[m,n] != -1)
return dp[m,n];

//if equal then move back and continue calculation, no operations required
if(w1[m] == w2[n])
return dp[m,n] = calculate(w1,w2,m-1,n-1,dp);

//replaced one and both are now same, so move both back
int a = calculate(w1,w2,m-1,n-1,dp); //replace
//insert elem in m,so move n back
int b = calculate(w1,w2,m,n-1,dp); // insert
//delete m elem so move m back but n as it is
int c = calculate(w1,w2,m-1,n,dp); // delete

//Take min of above operations + 1 (recent operation)
return dp[m,n] = 1 + Math.Min(a,Math.Min(b,c));
}
public int MinDistance(string word1, string word2) {

int m = word1.Length;
int n = word2.Length;
int[,] dp = new int[m,n];

//Initialization
for(int i=0; i< m; i++)
{
for(int j=0; j<n; j++)
{
dp[i,j] = -1;
}
}

int ans = calculate(word1,word2,m-1,n-1,dp);

return ans;
}
}``````

#### By Neha Singhal

Hi, my name is Neha singhal a software engineer and coder by profession. I like to solve coding problems that give me the power to write posts for this site.