Problem 53 · Dynamic Programming

Edit Distance

MediumClassic DSA & systems

01Problem

Given two strings, return the minimum number of single-character inserts, deletes, or substitutions to convert one into the other.

02Key insight

dp[i][j] = cost to turn a[:i] into b[:j]; match is free, otherwise 1 + min(insert, delete, replace). Only the previous row is needed, so space drops to O(min(m,n)).

03Solution

solution.pypython13 lines

def min_distance(a: str, b: str) -> int:
    if len(a) < len(b):
        a, b = b, a  # keep the row on the shorter string
    prev = list(range(len(b) + 1))
    for i, ca in enumerate(a, 1):
        cur = [i] + [0] * len(b)
        for j, cb in enumerate(b, 1):
            if ca == cb:
                cur[j] = prev[j - 1]
            else:
                cur[j] = 1 + min(prev[j], cur[j - 1], prev[j - 1])
        prev = cur
    return prev[-1]

Try it first.

TimeO(m*n)

SpaceO(min(m,n))

tests.py · 4 passing

tests.pypython4 lines

assert min_distance("horse", "ros") == 3
assert min_distance("intention", "execution") == 5
assert min_distance("", "abc") == 3
assert min_distance("same", "same") == 0

04Staff-level follow-up

Fuzzy search over millions of strings? Index with a BK-tree or trie + bounded Levenshtein automaton; if only distance <= k matters, use banded DP in O(k*n).