Edit Distance - Leetcode Solution

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
   • dp[i-1][j] represents the cost of deleting the character from word1.
   • dp[i][j-1] represents the cost of inserting the character into word1.
   • 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.

1