Edit Distance Leetcode Problem 72 [Python Solution]

Welcome back!

Today, we'll tackle the Edit Distance problem, a classic example of a 2-D dynamic programming challenge.

This problem is not only a brain teaser but also an excellent opportunity to dive into dynamic programming and get hands-on experience.

So, let's get started!

Problem Overview

The Edit Distance problem involves two strings, word1 and word2.

Our goal is to find the minimum number of operations required to transform word1 into word2.

The allowed operations are:

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

Here are a couple of examples to illustrate the problem:

Example 1:

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


Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
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')


Understanding Edit Distance Constraints

Before we dive into the solutions, let's understand the constraints of the problem:

• 0 <= word1.length, word2.length <= 500: Both input strings can be of varying lengths, but they won't exceed 500 characters.
• word1 and word2 consist of lowercase English letters: The input strings are composed of lowercase letters, making the problem manageable.

Now that we have a clear understanding of the problem, let's explore the solutions.

Edit Distance LeetCode Problem Solution

1. Bruteforce Approach

One way to tackle this problem is to use a recursive approach that considers all possibilities for each character.

We'll create a recursive function that tries all three operations: insert, delete, and replace, and returns the minimum of these possibilities.

def minDistance(word1: str, word2: str) -> int:
    # Base case 1: If word1 is empty, insert all characters from word2. if not word1:
        return len(word2)
    
    # Base case 2: If word2 is empty, delete all characters from word1. if not word2:
        return len(word1)

    # If the characters match, no operation is needed for this step.

if word1[0] == word2[0]:
        return minDistance(word1[1:], word2[1:])

    # If the characters don't match, consider all three operations.

insert_op = 1 + minDistance(word1, word2[1:])
    delete_op = 1 + minDistance(word1[1:], word2)
    replace_op = 1 + minDistance(word1[1:], word2[1:])

    # Return the minimum of the three operations.

return min(insert_op, delete_op, replace_op)

While this recursive approach works, it's highly inefficient for larger inputs due to its exponential time complexity.

Therefore, we'll move on to a more efficient dynamic programming solution.

2. An Efficient Approach with Dynamic Programming

We'll use a 2-D array, dp, to store the minimum number of operations needed to transform a substring of word1 into a substring of word2.

By filling up this array bottom-up, we can efficiently compute the minimum number of operations for the entire strings.

Here's the Python solution using dynamic programming:

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)

    # Initialize a 2-D array to store the minimum operations.

dp = [[float("inf")] * (n + 1) for _ in range(m + 1)]

    # Base cases: If one string is empty, insert or delete all characters.

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

    # Fill the dp array using bottom-up dynamic programming.

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

    return dp[0][0]

This dynamic programming approach has a time complexity of O(m * n) and a space complexity of O(m * n), where m and n are the lengths of word1 and word2, respectively.

Time and Space Complexity

• Time Complexity: O(m * n)
• Space Complexity: O(m * n)

Reasoning Behind Our Approach

We've discussed two approaches to solve the Edit Distance problem:

1. Bruteforce Approach: This recursive approach considers all possibilities for each character, which makes it straightforward but inefficient.

It has exponential time complexity and is not practical for larger inputs.

1. Efficient Approach with Dynamic Programming: We use a 2-D array to store the minimum operations needed to transform substrings of word1 into substrings of word2.

By filling up this array bottom-up, we efficiently compute the minimum number of operations for the entire strings.

This dynamic programming solution has a time complexity of O(m * n), where m and n are the lengths of word1 and word2, and it is space-efficient.

The dynamic programming approach is the most efficient and practical solution for this problem.

Related Interview Questions By Company:

• Rotting Oranges LeetCode
• Partition Labels LeetCode
• Combination Sum Iv LeetCode

Related Interview Questions By Difficulty:

• Edit Distance LeetCode
• Target Sum LeetCode
• Coin Change II LeetCode

Related Interview Questions By Category:

• Brick Wall LeetCode
• Maximal Square LeetCode
• Decode Ways LeetCode

Conclusion

In this guide, we explored the Edit Distance problem, which challenges us to find the minimum number of operations needed to transform one string into another.

We discussed two solutions: a bruteforce recursive approach and an efficient dynamic programming approach.

The dynamic programming solution, with a time complexity of O(m * n), is the recommended way to solve this problem.

It efficiently computes the minimum number of operations for the entire strings, making it suitable for practical applications.

I hope this guide has been helpful in understanding the Edit Distance problem and its solutions.

If you have any questions, feel free to ask in the comments, and don't forget to check out the LeetCode problem for further practice.

Happy coding!