# Classic DP solution in C; 12 ms; 15 lines

• int minof3(int x, int y, int z)
{
x = (x<y)?x:y;
return (x<z)?x:z;
}

int minDistance(char* w1, char* w2) {
//never trust the input
/*
if(w1 == NULL && w2==NULL) return 0;
else if(w1 == NULL)        return strlen(w2);
else if(w2 == NULL)        return strlen(w1);
*/

int l1 = strlen(w1);
int l2 = strlen(w2);

// dp[x][y] means the min edit distance from partial word1 (0..x-1) to partial word2 (0..y-1)
// please note this takes O(mn) space; O(n) solution also available because only last iteration of result needs to be stored
int dp[l1+1][l2+1];

// init the dynamic programming matrix
dp[0][0] = 0;
for(int i = 1; i<=l1; i++) dp[i][0] = i;
for(int j = 1; j<=l2; j++) dp[0][j] = j;

for(int i = 1; i<=l1; i++)
for(int j = 1; j<=l2; j++)
if(w1[i-1] != w2[j-1])
//different char; so adding/replacing/deleting all takes one more step
dp[i][j] = minof3(dp[i][j-1], dp[i-1][j-1], dp[i-1][j]) + 1;
else
//same char; so no need to replace it; adding/deleting one still takes one more step
dp[i][j] = minof3(dp[i][j-1]+1, dp[i-1][j-1], dp[i-1][j]+1);

return dp[l1][l2];
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.