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


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment