Leetcode Edit Distance problem solution

YASH PAL,

In this Leetcode Edit Distance problem solution we have 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:

  1. Insert a character
  2. Delete a character
  3. Replace a character
Leetcode Edit Distance problem solution

Problem solution in Python.

class Solution:
    def minDistance(self, A: str, B: str) -> int:
        if not A: return len(B)
        if not B: return len(A)
        m, n = len(A), len(B)
        dp = [[-1] * (n+1) for _ in range(m+1)]
        dp[0][0] = 0
        for i in range(1, m+1):
            dp[i][0] = i
            for j in range(1, n+1):
                dp[0][j] = j
                dp[i][j] = min(
                    dp[i-1][j]+1,
                    dp[i][j-1]+1,
                    dp[i-1][j-1]+(A[i-1]!=B[j-1])
                )
        return dp[-1][-1]

Problem solution in Java.

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m+1][n+1];
        for(int i=0; i<=m; i++) dp[i][0] = i;
        for(int j=0; j<=n; j++) dp[0][j] = j;
        for(int i=1; i<=m; i++){
            for(int j=1; j<=n; 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[m][n];
    }
}

Problem solution in C++.

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n=word1.length();
        int m=word2.length();
        int dp[n+5][m+5];
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
        {
            dp[i][0]=i;
        }
        for(int i=0;i<=m;i++)
        {
            dp[0][i]=i;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(word1[i-1]==word2[j-1])
                {
                    dp[i][j]=min({dp[i-1][j-1],dp[i-1][j]+1,dp[i][j-1]+1});
                }
                else
                {
                    dp[i][j]=min({dp[i-1][j-1]+1,dp[i-1][j]+1,dp[i][j-1]+1});
                }
            }
        }
        return dp[n][m];
    }
};

Problem solution in C.

int minDistance(char * word1, char * word2){
    int m = strlen(word2);
    char *s1 = word1;
    char *s2 = word2;
    
    int *mat = malloc(sizeof(int) * (m+1));
    
    for(int i=0; i<=m; ++i) {
        mat[i] = i;
    }
    
    for(int i=1; *s1; ++i, ++s1) {
        s2 = word2;
        int pre = i-1;
        mat[0] = i;
        for(int j=1; j<=m; ++s2, ++j) {
            int tmp = mat[j];
            int min = *s2 == *s1 ? pre : pre+1;
            min = min < mat[j-1]+1 ? min : mat[j-1]+1;    
            mat[j] = mat[j]+1 < min ? mat[j]+1 : min;
            pre = tmp;
        }
    }

    return mat[m];
}

coding problems