How do you approach Edit Distance?

Use 2D DP where dp[i][j] = min operations to convert word1[0..i-1] to word2[0..j-1].

What is the time complexity of Edit Distance?

Time complexity: O(m n). Space complexity: O(m n) or O(min(m, n)) with optimization.

What are common mistakes on Edit Distance?

Iterating the dimensions in an order that reads a cell before it has been written. Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input. Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.

gitGood.dev

← Back to problems

Edit Distance

HardAlgorithms

Description

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

Insert a character
Delete a character
Replace a character

Example 1

Input: word1 = "horse", word2 = "ros"

Output: 3

Explanation: horse -> rorse (replace "h" with "r") -> rose (remove "r") -> ros (remove "e")

Example 2

Input: word1 = "intention", word2 = "execution"

Output: 5

Explanation: intention -> inention (remove "t") -> enention (replace "i" with "e") -> exention (replace "n" with "x") -> exection (replace "n" with "c") -> execution (insert "u")

Constraints

- 0 <= word1.length, word2.length <= 500 - word1 and word2 consist of lowercase English letters.

Edit Distance: approach, complexity and pitfalls

A hard dynamic programming problem, graded against 6 test cases (3 of them hidden).

The pattern: Dynamic Programming

Overlapping subproblems solved once and reused - the pattern candidates fear most.

Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.

If you are stuck

Show the 3-step hint ladder

Use 2D DP where dp[i][j] = min operations to convert word1[0..i-1] to word2[0..j-1].
If characters match, dp[i][j] = dp[i-1][j-1].
Otherwise, take min of insert, delete, replace operations.

The optimal approach

Show the approach: Dynamic Programming

dp[i][j] represents the minimum edits to convert word1[0..i-1] to word2[0..j-1].

- If word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1]

- Otherwise: min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

Time: O(m * n)
Space: O(m * n) or O(min(m, n)) with optimization

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty string. An empty string is passed, so index reads and any assumption of at least one character are tested.

Common Dynamic Programming mistakes

These apply to the pattern as a whole, not just this problem.

Iterating the dimensions in an order that reads a cell before it has been written.
Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input.
Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.