Skip to content
GKgkml.dev
← Problem set
#72MediumDynamic programming

Edit Distance

The tell: Minimum operations to transform one string into another.

How you get there

  1. 1dp[i][j] is the cost of turning the first i characters into the first j.
  2. 2Matching characters cost nothing and move diagonally.
  3. 3Otherwise take one plus the cheapest of replace, delete or insert.

Solution

Python
def min_distance(word1: str, word2: str) -> int:
    prev = list(range(len(word2) + 1))

    for i, c1 in enumerate(word1, start=1):
        cur = [i] + [0] * len(word2)
        for j, c2 in enumerate(word2, start=1):
            if c1 == c2:
                cur[j] = prev[j - 1]
            else:
                cur[j] = 1 + min(prev[j - 1], prev[j], cur[j - 1])   # replace, delete, insert
        prev = cur
    return prev[-1]
Time
O(n · m)
Space
O(m)

What goes wrong

Initialising the first row and column to zero instead of their indices gives wrong answers for empty prefixes.

Test yourself on DSANext: Word Break →