Edit Distance Problem Solution

Edit Distance Problem: 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 :

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')

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];
}