Comparing word1[0:i] to word2[0:j]: if the last characters match, no operation is needed there — the answer is the same as for the shorter prefixes word1[0:i-1] and word2[0:j-1]. If they don’t match, one operation is spent, and it is the best of the three possible next moves: delete from word1, insert into word1 (equivalently, delete from word2), or replace.
Brute Force Recursion
Time O(3^(m+n))Space O(m+n)At each pair of positions, if the current characters match, move both pointers for free. Otherwise, try all three operations and recurse, taking the minimum plus one.
class Solution: def minDistance(self, word1: str, word2: str) -> int: def rec(i: int, j: int) -> int: if i == len(word1): return len(word2) - j if j == len(word2): return len(word1) - i if word1[i] == word2[j]: return rec(i + 1, j + 1) delete = rec(i + 1, j) insert = rec(i, j + 1) replace = rec(i + 1, j + 1) return 1 + min(delete, insert, replace) return rec(0, 0)Every mismatch branches three ways, and the same (i, j) pair recurs across many different operation orders — exponential blow-up.
2-D DP Table (Bottom-Up)
OptimalTime O(m·n)Space O(m·n)dp[i][j] is the edit distance between word1[0:i] and word2[0:j]. Turning any prefix into an empty string costs one delete per character, so row 0 and column 0 are just 0, 1, 2, 3, .... Every other cell either copies the diagonal for free (characters match) or takes the best of its three neighbors plus one.
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]Filling the table on the statement’s first example, word1 = "horse", word2 = "ros". Watch each cell read its three neighbours: a match copies the diagonal for free, a mismatch pays 1 plus the cheapest neighbour.
h != r, so dp[1][1] = 1 + the cheapest neighbour. Up 1, left 1, diag 0. Replacing wins at 1.
Complexity: each of the (m+1)·(n+1) cells does O(1) work → O(m·n) time, O(m·n) space.
1-D Rolling Array
Time O(m·n)Space O(n)Row i only reads from row i-1 (diagonal and directly above) and from row i itself (directly to the left). Keeping just the previous row and the row being built is enough: the diagonal dp[i-1][j-1] is still available in prev while curr is filled.
class Solution: def minDistance(self, word1: str, word2: str) -> int: m, n = len(word1), len(word2) prev = list(range(n + 1)) for i in range(1, m + 1): curr = [i] + [0] * n 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]Same O(m·n) time, but only two rows of length n + 1 are alive at once — O(n) space.