Edit Distance

Problem

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. You have three operations: insert a character, delete a character, or replace a character.

Examples

The brute-force approach

Recursion: at each step, if characters match, recurse on the remaining strings. Otherwise try all three operations and take the minimum.

def min_dist(i, j):   # cost to convert word1[i:] to word2[j:]
    if i == len(word1): return len(word2) - j
    if j == len(word2): return len(word1) - i
    if word1[i] == word2[j]:
        return min_dist(i+1, j+1)
    return 1 + min(
        min_dist(i+1, j),    # delete from word1
        min_dist(i, j+1),    # insert into word1
        min_dist(i+1, j+1),  # replace
    )

O(3^(m+n)) — exponential without memoization.

Spotting the pattern

This is a Dynamic Programming problem. The key question to ask yourself:

The three operations (replace, delete, insert) correspond to three cells in the DP table. Which cell maps to which operation?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.