We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Edit Distance

Difficulty: Medium

Problem Description

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

Key Insights

  • The problem is a classic example of dynamic programming.
  • We can use a 2D array (dp) where dp[i][j] represents the minimum edit distance between the first i characters of word1 and the first j characters of word2.
  • The solution builds upon smaller subproblems, considering the three operations: insertion, deletion, and replacement.

Space and Time Complexity

Time Complexity: O(m * n) where m and n are the lengths of word1 and word2, respectively.
Space Complexity: O(m * n) for the dp array.

Solution

To solve the problem, we utilize a 2D array to store intermediate results of the edit distances between substrings of word1 and word2. The algorithm iteratively fills this array based on the defined operations:

  1. If the characters match, no new operation is needed, and we carry over the previous value.
  2. If they don't match, we consider the minimum cost of the three possible operations (insert, delete, replace) and add one to account for the current operation. This leads to an efficient calculation of the minimum edit distance.

Code Solutions

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    # Create a 2D array for storing the edit distances
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Fill the first column and first row
    for i in range(m + 1):
        dp[i][0] = i  # Deleting all characters from word1
    for j in range(n + 1):
        dp[0][j] = j  # Inserting all characters to word1 to form word2
    
    # Compute the edit distances
    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]  # No operation needed
            else:
                dp[i][j] = min(dp[i - 1][j] + 1,    # Delete
                               dp[i][j - 1] + 1,    # Insert
                               dp[i - 1][j - 1] + 1)  # Replace

    return dp[m][n]
← Back to All Questions