Leetcode Edit Distance Problem Solution

In this 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

Problem solution in Python.

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [[0 for j in range(len(word2)+1)] for i in range(len(word1)+1)]
        #When a string is empty, the edit distance will be the current length of the other string.
        for j in range(1, len(word2)+1): 
            dp[0][j] = j
        for i in range(1, len(word1)+1):
            dp[i][0] = i
        
        for i, char1 in enumerate(word1, 1):
            for j, char2 in enumerate(word2, 1):
                if char1 == char2:
                    dp[i][j] = dp[i-1][j-1] 
                else:
                    #insert, replace, delete
                    dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1 
        
        return dp[-1][-1]

Problem solution in Java.

class Solution {
    public int minDistance(String word1, String word2) {
        int l1 = word1.length();
        int l2 = word2.length();
        int[][] dp = new int[l1+1][l2+1];
        
        // Base cases
        // Initializing First row
        for(int i=0; i <= l2; i++)
            dp[0][i] = i;        
        // Initializing First col
        for(int i=0; i <= l1; i++)
            dp[i][0] = i;
        
        for(int i=1; i <= l1; i++){
            for(int j=1; j <= l2; j++){
                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-1][j-1], // replace
                                            Math.min(dp[i-1][j], // delete
                                                     dp[i][j-1]) // insert
                                           ); 
            }
        }
        
        return dp[l1][l2];
    }
}

Problem solution in C++.

class Solution {
public:
    int mini(int a, int b, int c){
        return min(a, min(b,c));
    }
    int foo(vector<vector<int>> &dp, string w1, string w2, int x, int y ) {
        if(x<0 && y<0)
            return 0;
        if(x<0){
            return y+1;
        }
        if(y<0){
            return x+1;
        }
        
        if(dp[x][y] != 0)
            return dp[x][y];
        
        if(w1[x] == w2[y]){
            dp[x][y] = foo(dp, w1,w2,x-1,y-1);
        }else{
            dp[x][y] = 1+ mini(foo(dp,w1,w2,x,y-1),
                          foo(dp,w1,w2,x-1,y),
                           foo(dp,w1,w2,x-1,y-1)
                          );
        }
        return dp[x][y];
    }
    int minDistance(string word1, string word2) {
        int n = word1.length();
        int m = word2.length(); 
        
       vector<vector<int>>dp;
        for(int i=0;i<n;i++){
            vector<int>v;
            for(int j=0;j<m;j++)
                v.push_back(0);
            dp.push_back(v);
        }
        
        return foo(dp, word1, word2, n-1, m-1);
        
    }
};

Problem solution in C.

int min(int a, int b)
{
    return a < b ? a : b;
}
 
int minDistance(char * word1, char * word2)
{
    if(strlen(word1) == 0 && strlen(word2) == 0)
    {
        return 0;
    }
    int* dp = (int*)malloc(sizeof(int) * (strlen(word1)+1));
    dp[0] = 0;
    for(int i = 1; i < strlen(word1) + 1; ++i)
    {
        dp[i] = i;
    }
    for(int j = 1; j < strlen(word2) + 1; ++j)
    {
        int tmp = dp[0];
        dp[0] = j;        
        for(int i = 1; i < strlen(word1) + 1; ++i)
        {
            int tmp0 = dp[i];
            if(word1[i-1] == word2[j-1])
            {
                dp[i] = tmp;
            }
            else
            {
                dp[i] = min(tmp, min(dp[i], dp[i-1])) + 1;
            }
            tmp = tmp0;
        }
    }
    return dp[strlen(word1)];
}