Edit Distance

PracticeNeetCode ↗LeetCode ↗

Given two strings word1 and word2, return the minimum number of single-character insert, delete, or replace operations needed to turn word1 into word2.

Example

Key Pointers

• Define dp[i][j] as the min edits to turn word1[:i] into word2[:j] — the answer for the full strings sits in the bottom-right corner.
• If the last characters already match, no new edit is needed there — the answer is inherited straight from the diagonal.
• If they don't match, the best move is 1 (for this edit) plus the cheapest of the three neighboring subproblems, each representing insert, delete, or replace.

Step-by-Step Analysis

1. Build a grid sized (len(word1)+1) × (len(word2)+1).
2. Base cases: turning an i-length prefix into empty costs i deletions; turning empty into a j-length prefix costs j insertions.
3. For each cell, if the corresponding characters match, copy the diagonal value directly.
4. Otherwise, take 1 + min(delete, insert, replace) — the cell above, the cell to the left, and the diagonal cell, respectively.
5. The bottom-right cell holds the final edit distance.

Complexity

Time: O(m · n) — Space: O(m · n)

Code

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], dp[i][j - 1], dp[i - 1][j - 1])

    return dp[m][n]

Code Explanation

How the solution above works, piece by piece.

1. dp[i][j] = fewest edits to turn word1[:i] into word2[:j].
2. Base cases: turning i letters into nothing takes i deletions; building j letters from nothing takes j insertions.
3. If the last letters match, no edit is needed for them: copy the diagonal.
4. Otherwise 1 + the cheapest of delete (dp[i-1][j]), insert (dp[i][j-1]) or replace (dp[i-1][j-1]).
5. O(m × n) time and space.

Visual Walkthrough

Running it on word1 = "horse", word2 = "ros":

Video Explanation

NeetCode — Edit Distance, LeetCode 72