Edit Distance

Problem

Given two strings word1 and word2, return the minimum number of single-character edits needed to turn word1 into word2. The allowed edits are:

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

This minimum is the classic Levenshtein distance.

Examples

• word1 = "horse", word2 = "ros" → 3 — horse → rorse (replace h→r), rorse → rose (delete r), rose → ros (delete e).
• word1 = "intention", word2 = "execution" → 5 — five edits align the two words optimally.
• word1 = "", word2 = "abc" → 3 — three inserts build abc from nothing.

Constraints

• 0 <= word1.length, word2.length <= 500
• Both strings consist of lowercase English letters.

With lengths up to 500 each, the expected solution is O(m × n) — a grid of at most 250,000 cells.

Think about it first

TL;DR

Levenshtein DP over prefix pairs (i, j) — O(m × n) time, O(min(m, n)) space after rolling to two rows.

Approach 1 — Brute-force recursion

Compare the last characters of the two prefixes. If they match, drop both and recurse. If not, try all three edits — replace (drop both, +1), delete from word1 (drop one, +1), insert into word1 (drop one from word2, +1) — and take the cheapest.

def minDistance(word1: str, word2: str) -> int:

    def dfs(i: int, j: int) -> int:
        if i == 0:
            return j           # insert the remaining j chars
        if j == 0:
            return i           # delete the remaining i chars
        if word1[i - 1] == word2[j - 1]:
            return dfs(i - 1, j - 1)
        replace = dfs(i - 1, j - 1)
        delete = dfs(i - 1, j)
        insert = dfs(i, j - 1)
        return 1 + min(replace, delete, insert)

    return dfs(len(word1), len(word2))

Complexity: O(3^(m+n)) time in the worst case (three-way branch at every mismatch), O(m+n) recursion depth.

This is too slow for the constraints: for two length-500 strings with no matching characters, the three-way branching makes the recursion exponential.

Approach 2 — Top-down memoization

The recursion depends only on (i, j), and there are just (m+1)(n+1) distinct pairs. Caching each result reduces the exponential recursion to one evaluation per pair.

from functools import lru_cache


def minDistance(word1: str, word2: str) -> int:

    @lru_cache(maxsize=None)
    def dfs(i: int, j: int) -> int:
        if i == 0:
            return j
        if j == 0:
            return i
        if word1[i - 1] == word2[j - 1]:
            return dfs(i - 1, j - 1)
        return 1 + min(dfs(i - 1, j - 1), dfs(i - 1, j), dfs(i, j - 1))

    return dfs(len(word1), len(word2))

Complexity: O(m × n) time and space.

Approach 3 — Bottom-up 2-D table

dp[i][j] = edit distance between word1[:i] and word2[:j] (the first i and first j characters).

Each cell depends on three already-computed neighbors:

flowchart LR
  diag["dp[i-1][j-1]<br/>replace / match"] --> cur["dp[i][j]"]
  up["dp[i-1][j]<br/>delete from word1"] --> cur
  left["dp[i][j-1]<br/>insert into word1"] --> cur

Recurrence:

dp[i][0] = i,  dp[0][j] = j              # to/from empty string costs its length
if word1[i-1] == word2[j-1]:
    dp[i][j] = dp[i-1][j-1]              # free: characters already match
else:
    dp[i][j] = 1 + min( dp[i-1][j-1],    # replace
                        dp[i-1][j],       # delete from word1
                        dp[i][j-1] )      # insert into word1

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j - 1],
                                   dp[i - 1][j],
                                   dp[i][j - 1])
    return dp[m][n]

Walkthrough on word1 = "horse", word2 = "ros". The filled grid (rows = horse prefixes, cols = ros prefixes):

dp[5][3] = 3 — matching the three edits from the examples.

Complexity: O(m × n) time, O(m × n) space.

Approach 4 — Space-optimized two rows

dp[i][j] reads only row i-1 and the current row’s left neighbor. Keep the previous row and build the current one; that drops space to O(n).

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    prev = list(range(n + 1))                  # dp[0][j] = j
    for i in range(1, m + 1):
        curr = [i] + [0] * n                    # dp[i][0] = i
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                curr[j] = prev[j - 1]
            else:
                curr[j] = 1 + min(prev[j - 1], prev[j], curr[j - 1])
        prev = curr
    return prev[n]

Complexity: O(m × n) time, O(n) space. (Swap the strings so the shorter one drives n for O(min(m, n)) space.)

Common pitfalls

• Mixing up which neighbor is insert vs delete — dp[i-1][j] shrinks word1 (delete), dp[i][j-1] shrinks word2 (insert into word1). They cost the same, but swapping them reverses the direction of the reconstructed edits.
• Skipping the base row/column — an empty prefix must cost the length of the other, or the whole table is off.
• Adding 1 on a match — when characters are equal the cost carries over unchanged from the diagonal; adding 1 there overcounts.
• In the rolled version, reset curr[0] = i every new row, or the base column drifts.

Pattern takeaway

Two-string alignment problems (edit distance, LCS, interleaving) all live on a (prefix of A, prefix of B) grid. Compare the two current characters: a match walks the diagonal for free, a mismatch pays a fixed cost and chooses among the three orthogonal/diagonal neighbors. Every cell depends only on the previous row, so O(n) space is always available.