Edit Distance · DSA Prep

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 for word1 = "ab", word2 = "bc" (a small illustrative case):

1 / 5

comparingseenresult

Base case: turning an i-character prefix into empty (or vice versa) costs i deletions (or insertions).

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). A single reused row works as long as the “diagonal” value (dp[i-1][j-1]) is saved off before it gets overwritten by the current row’s computation.

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.