Edit Distance

Solution For Edit Distance

The Edit Distance problem on LeetCode is also known as the minimum edit distance problem or the Levenshtein distance problem. It is a classic problem in computer science that deals with finding the minimum number of operations required to convert one string into another. These operations include insertion, deletion, and substitution of characters.

The problem statement on LeetCode is as follows:

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

Let’s take an example to understand the problem better.

Example 1:

Input: word1 = “horse”, word2 = “ros”
Output: 3
Explanation:
– Replace ‘h’ with ‘r’
– Delete ‘o’
– Delete ‘e’

One approach to solving this problem is to use dynamic programming. We can create a 2-D array dp where dp[i][j] represents the minimum number of operations required to convert the substring word1[0…i-1] to the substring word2[0…j-1].

We can fill up the table in a bottom-up manner. Here’s how the dp array would be filled:

  1. Initialization: dp[0][0] = 0, dp[i][0] = i (0<=i<=len(word1)), dp[0][j] = j (0<=j<=len(word2))
  2. If the characters at word1[i-1] and word2[j-1] are equal, then dp[i][j] = dp[i-1][j-1]
  3. If the characters at word1[i-1] and word2[j-1] are not equal, then dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
  4. dp[i-1][j] represents the cost of deleting the character from word1.
  5. dp[i][j-1] represents the cost of inserting the character into word1.
  6. dp[i-1][j-1] represents the cost of replacing the character in word1 with the character in word2.

The final answer will be stored in dp[len(word1)][len(word2)].

Here’s the Python code for the Edit Distance problem:

“`
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
dp = [[0 for _ in range(n+1)] for _ in range(m+1)]

    # initialization
    for i in range(m+1):
        dp[i][0] = i
    for j in range(n+1):
        dp[0][j] = j

    for i in range(1, m+1):
        for j in range(1, n+1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

    return dp[m][n]

“`

The time complexity of the above algorithm is O(mn) where m and n are the lengths of word1 and word2 respectively. The space complexity is also O(mn) since we are using a 2-D array to store the intermediate results.

Step by Step Implementation For Edit Distance

class Solution {
    public int minDistance(String word1, String word2) {
        // if one of the strings is empty
        if (word1.length() == 0 || word2.length() == 0) {
            // return the length of the other string
            return word1.length() == 0 ? word2.length() : word1.length();
        }
        
        // create a 2D array to store the edit distances
        // for all substrings of word1 and word2
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        
        // initialize the 2D array
        // the edit distance between an empty string and
        // a non-empty string is the length of the non-empty string
        for (int i = 0; i <= word1.length(); i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= word2.length(); j++) {
            dp[0][j] = j;
        }
        
        // fill in the 2D array
        // i and j represent the lengths of the substrings
        // of word1 and word2 respectively
        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <= word2.length(); j++) {
                // if the ith character of word1 equals the
                // jth character of word2
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    // then the edit distance between the
                    // ith and jth substrings of word1 and word2
                    // is the same as the edit distance between
                    // the (i - 1)th and (j - 1)th substrings
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // otherwise, the edit distance is the minimum
                    // of the edit distances between the (i - 1)th
                    // and jth substrings, the ith and (j - 1)th
                    // substrings, and the (i - 1)th and (j - 1)th
                    // substrings, plus 1
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            }
        }
        
        // return the edit distance between word1 and word2
        return dp[word1.length()][word2.length()];
    }
}
def minDistance(word1, word2): 
    
    # Create a table to store results of subproblems 
    dp = [[0 for x in range(len(word2)+1)] for x in range(len(word1)+1)] 
  
    # Fill d[][] in bottom up manner 
    for i in range(len(word1)+1): 
        for j in range(len(word2)+1): 
  
            # If first string is empty, only option is to 
            # insert all characters of second string 
            if i == 0: 
                dp[i][j] = j    # Min. operations = j 
  
            # If second string is empty, only option is to 
            # remove all characters of second string 
            elif j == 0: 
                dp[i][j] = i    # Min. operations = i 
  
            # If last characters are same, ignore last char 
            # and recur for remaining string 
            elif word1[i-1] == word2[j-1]: 
                dp[i][j] = dp[i-1][j-1] 
  
            # If the last character is different, consider all 
            # possibilities and find the minimum 
            else: 
                dp[i][j] = 1 + min(dp[i][j-1],        # Insert 
                                   dp[i-1][j],        # Remove 
                                   dp[i-1][j-1])    # Replace 
  
    return dp[len(word1)][len(word2)]
var minDistance = function(word1, word2) {
    // create a matrix to store the results of each subproblem
    // (i.e. the edit distance between each prefix of word1 and 
    // each prefix of word2)
    let matrix = [];
    
    // fill in the first row and column of the matrix
    for (let i = 0; i <= word1.length; i++) {
        matrix.push([]);
        matrix[i][0] = i;
    }
    for (let j = 0; j <= word2.length; j++) {
        matrix[0][j] = j;
    }
    
    // fill in the rest of the matrix
    for (let i = 1; i <= word1.length; i++) {
        for (let j = 1; j <= word2.length; j++) {
            // if the ith character of word1 equals the jth character of word2
            // then the edit distance between the prefixes word1[0..i] and word2[0..j]
            // is the same as the edit distance between the prefixes word1[0..i-1] and word2[0..j-1]
            if (word1[i-1] === word2[j-1]) {
                matrix[i][j] = matrix[i-1][j-1];
            }
            // otherwise, the edit distance is one more than the minimum of
            // the edit distances between the prefixes word1[0..i-1] and word2[0..j],
            // between the prefixes word1[0..i] and word2[0..j-1], and
            // between the prefixes word1[0..i-1] and word2[0..j-1]
            else {
                matrix[i][j] = Math.min(matrix[i-1][j], matrix[i][j-1], matrix[i-1][j-1]) + 1;
            }
        }
    }
    
    // return the edit distance between the full strings word1 and word2
    return matrix[word1.length][word2.length];
};
int minDistance(string word1, string word2) 
{
    int len1 = word1.size();
    int len2 = word2.size();
 
    // len1+1, len2+1, because finally return dp[len1][len2]
    int dp[len1 + 1][len2 + 1];
 
    for (int i = 0; i <= len1; i++) {
        dp[i][0] = i;
    }
 
    for (int j = 0; j <= len2; j++) {
        dp[0][j] = j;
    }
 
    //iterate though, and check last char
    for (int i = 0; i < len1; i++) {
        char c1 = word1[i];
        for (int j = 0; j < len2; j++) {
            char c2 = word2[j];
 
            //if last two chars equal
            if (c1 == c2) {
                //update dp value for +1 length
                dp[i + 1][j + 1] = dp[i][j];
            } else {
                int replace = dp[i][j] + 1;
                int insert = dp[i][j + 1] + 1;
                int delete = dp[i + 1][j] + 1;
 
                int min = replace > insert ? insert : replace;
                min = delete > min ? min : delete;
                dp[i + 1][j + 1] = min;
            }
        }
    }
 
    return dp[len1][len2];
}
public class Solution { 
    public int MinDistance(string word1, string word2) {
        int n = word1.Length;
        int m = word2.Length;
 
        // Create a table to store results of subproblems 
        int[,] dp = new int[n + 1, m + 1];
 
        // Fill d[][] in bottom up manner 
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                // If first string is empty, only option is to 
                // insert all characters of second string 
                if (i == 0)
                    dp[i, j] = j;  // Min. operations = j 
 
                // If second string is empty, only option is to 
                // remove all characters of second string 
                else if (j == 0)
                    dp[i, j] = i; // Min. operations = i 
 
                // If last characters are same, ignore last char 
                // and recur for remaining string 
                else if (word1[i - 1] == word2[j - 1])
                    dp[i, j] = dp[i - 1, j - 1];
 
                // If the last character is different, consider all 
                // possibilities and find the minimum 
                else
                    dp[i, j] = 1 + Math.Min(dp[i, j - 1],  // Insert 
                                            Math.Min(dp[i - 1, j],  // Remove 
                                            dp[i - 1, j - 1])); // Replace 
            }
        }
 
        return dp[n, m];
    }
}


Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]