Edit Distance — InterviewPrepKit

Solving tips

Recognize Levenshtein distance on a (prefix of A, prefix of B) grid: dp[i][j] = edits to turn word1[:i] into word2[:j].
On a character match walk the diagonal for free (dp[i-1][j-1]); on a mismatch pay 1 + min of the three neighbors: diagonal=replace, dp[i-1][j]=delete, dp[i][j-1]=insert.
Seed the base row/column with dp[i][0]=i and dp[0][j]=j (converting to/from empty costs its length); target O(m*n) time, O(min(m,n)) space with two rows.
Pitfall: adding 1 on a match (it carries over unchanged) or mixing up which neighbor is insert vs delete.

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

Hint 1

Compare the two strings from one end. If the last characters match, they cost nothing — recurse on the two shorter prefixes. If they differ, you must pay 1 for one of insert / delete / replace and recurse on the correspondingly shortened strings.

Hint 2

The subproblem is "edit distance between `word1`'s first `i` characters and `word2`'s first `j` characters." Two indices → a 2-D table `dp[i][j]`. Insert / delete / replace each move you to a different neighboring cell.

Hint 3

If `word1[i-1] == word2[j-1]`: `dp[i][j] = dp[i-1][j-1]`. Otherwise `dp[i][j] = 1 + min(dp[i-1][j-1]` (replace)`, dp[i][j-1]` (insert)`, dp[i-1][j]` (delete)`)`. Base row/column: converting to/from an empty string costs its length.

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

Intuition: 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.

class Solution:
    def minDistance(self, 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.

Why the constraints kill it: for two length-500 strings with no matches, the branching factor explodes far beyond any time limit.

Approach 2 — Top-down memoization

The insight: the recursion only depends on (i, j), and there are just (m+1)(n+1) such pairs. Cache each — the 2-D memo turns the exponential tree linear in the grid size.

from functools import lru_cache


class Solution:
    def minDistance(self, 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

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

2-D 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

class Solution:
    def minDistance(self, 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):

	""	r	o	s
""	0	1	2	3
h	1	1	2	3
o	2	2	1	2
r	3	2	2	2
s	4	3	3	2
e	5	4	4	3

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

The insight: 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).

class Solution:
    def minDistance(self, 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 are symmetric in cost but get the direction of the walkthrough wrong if confused.
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.