Minimum Edit Distance

Hi geeks! In this article, we going to see about Minimum Edit Distance problem with Dynamic Programming Approach.

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

  1. Insert a character
  2. Delete a character
  3. Replace a character

Example 1:

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

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

C# Solution

public class Solution {
    public int MinDistance(string word1, string word2) {
        //Boundary cases
        if(string.IsNullOrEmpty(word1) && string.IsNullOrEmpty(word2))
            return 0;
        else if(string.IsNullOrEmpty(word1))
            return word2.Length;
        else if(string.IsNullOrEmpty(word2))
            return word1.Length;
        int m = word1.Length+1;
        int n =  word2.Length+1;
        int[,] dp = new int[m,n];
        for(int i=0;i<m;i++)
            //Row wise
            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[i-1] == word2[j-1])
                    dp[i,j] = dp[i-1,j-1];
                    dp[i,j] = Math.Min(Math.Min(dp[i,j-1],dp[i-1,j]),dp[i-1,j-1]) + 1;  
        return dp[m-1,n-1];

Time Complexity: O(m*n)

Space Complexity: O(m*n)

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s