Katkat
Back

Compute Edit Distance

AmazonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Tests dynamic programming and string manipulation by calculating the minimum number of single-character edits (insertions, deletions, substitutions) needed to transform one string into another.

Problem Statement

Given two strings word1 and word2, return the minimum number of operations required to convert word1 into word2.

You have the following three operations permitted on a word:

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

Function Signature

def min_distance(word1: str, word2: str) -> int:
    pass

Input & Output

  • Input: Two strings word1 and word2 consisting of lowercase English letters.
  • Output: An integer representing the minimum edit distance.

Constraints

  • `0 <= len(word1), len(word2) rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e')

### Example 2

```text
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 -> exenution (replace 't' with 'u')
exenution -> execution (insert 'c')

Edge Cases to Consider

  • Either string or both strings are empty.
  • Both strings are already identical.
  • One string is a strict prefix or suffix of the other.

Hints

Hint 1

Define a 2D table where dp[i][j] represents the minimum operations required to convert word1[0:i] to word2[0:j].

Hint 2

If the current characters match (word1[i-1] == word2[j-1]), no new operation is needed, so dp[i][j] = dp[i-1][j-1].

Hint 3

If the characters differ, take the minimum of inserting (dp[i][j-1]), deleting (dp[i-1][j]), or replacing (dp[i-1][j-1]), and add 1.

Follow-up questions

  • Can you optimize the space complexity from O(m * n) to O(min(m, n))?
  • How would you reconstruct and return the exact sequence of edit steps instead of just the count?
  • How would you adapt the algorithm if operations had varying costs (e.g., deletion costs 2, insertion costs 1, replacement costs 3)?