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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Edit Distance

Number: 72

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Microsoft, Meta, Flipkart, Zoho, HashedIn, TikTok, LinkedIn, Cisco, Infosys, Arcesium, Deloitte, Adobe, Bloomberg, Snap, Apple, Rubrik

Problem Description

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. The allowed operations are:

  • Insert a character
  • Delete a character
  • Replace a character

For example:

  • Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: Replace 'h' with 'r' -> Delete 'r' -> Delete 'e'
  • Input: word1 = "intention", word2 = "execution" Output: 5

Key Insights

  • This is a classic dynamic programming problem.
  • Use a 2D DP table where dp[i][j] represents the minimum edit distance between word1[0…i-1] and word2[0…j-1].
  • Base cases: converting an empty string to a string of length j requires j insertions, and vice versa.
  • Transition: If characters match then dp[i][j] = dp[i-1][j-1], otherwise take minimum among insertion, deletion, and replacement operations and add 1.

Space and Time Complexity

Time Complexity: O(mn), where m and n are the lengths of word1 and word2 respectively. Space Complexity: O(mn) due to the DP table used for storing computed distances.

Solution

We use a dynamic programming approach by constructing a 2D table dp of size (m+1) x (n+1), where m and n are the lengths of word1 and word2. Each dp[i][j] holds the minimum number of operations needed to convert the first i characters of word1 to the first j characters of word2. The algorithm includes the following steps:

  1. Initialize the base cases:
    • dp[0][j] = j (converting an empty word1 to j characters of word2 requires j insertions)
    • dp[i][0] = i (converting i characters of word1 to an empty word2 requires i deletions)
  2. Iterate over each character in word1 and word2:
    • If the current characters are equal, no additional operation is needed and dp[i][j] = dp[i-1][j-1].
    • Otherwise, choose the best operation among insertion (dp[i][j-1]), deletion (dp[i-1][j]), or substitution (dp[i-1][j-1]) and add 1.
  3. The answer is found in dp[m][n].

This method reliably computes the edit distance using a systematic DP approach, ensuring that all subproblems are solved and reused efficiently.

Code Solutions

# Python solution to compute the Edit Distance
def minDistance(word1, word2):
    m = len(word1)
    n = len(word2)
    
    # Initialize the DP table with size (m+1) x (n+1)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Base cases: transform word1[0:i] to empty word2 requires i deletions
    for i in range(m + 1):
        dp[i][0] = i
    # Base cases: transform empty word1 to word2[0:j] requires j insertions
    for j in range(n + 1):
        dp[0][j] = j
        
    # Fill up the dp table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            # If the characters are the same, no new operation is needed.
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                # consider insertion, deletion, and replacement
                dp[i][j] = 1 + min(dp[i][j - 1],   # Insert
                                   dp[i - 1][j],   # Delete
                                   dp[i - 1][j - 1]) # Replace
    return dp[m][n]

# Example usage:
print(minDistance("horse", "ros"))
← Back to All Questions